Paths and Circuits

Section 10.2 Paths and Circuits

The origin story for this section is the Konigsberg Bridge Problem, which involves seven bridges, as pictured in Figure 10.2.1. The story is that the challenge of Konigsberg was to try to traverse all the bridges, without repeating one, and return to where you started. Euler found a way to represent the problem as a graph, also pictured. The vertices are the land masses and the edges are the bridges. This representation makes it easier to try to answer the question. Before moving on, try to solve the bridge problem by finding a route through the graph that starts and ends at some vertex and traverses each edge exactly once.

🔗

Figure 10.2.1. Konigsberg bridge problem, $G$
🔗

Definition 10.2.2.

For each of the following terms we have a list of vertices and edges,

v_{0} e_{1} v_{1} e_{2} \dots e_{n} v_{v},

that represent a way to traverse through the graph. So, for example,

v_{0}

must be an endpoint of

e_{1},

v_{1}

must be an endpoint of

e_{1}

and

e_{2},

etc. For each of the following terms we indicate whether we can repeat vertices and/or edges in the list.

🔗

A walk from $v$ to $w$ has $v = v_{0}, w = v_{n} .$ It can repeat edges and vertices. It can begin at any vertex and end at any vertex.
A trail from $v$ to $w$ has $v = v_{0}, w = v_{n} .$ It cannot repeat edges. It can begin at any vertex and end at any vertex.
A path from $v$ to $w$ has $v = v_{0}, w = v_{n} .$ It cannot repeat edges or vertices. It can begin at any vertex and end at any vertex.
A closed walk must start and end at the same vertex $v,$ $v = v_{0}, v = v_{n} .$ It can repeat edges and vertices.
A circuit must start and end at the same vertex $v,$ $v = v_{0}, v = v_{n} .$ It cannot repeat edges. It can repeat vertices.
A simple circuit must start and end at the same vertex $v,$ $v = v_{0}, v = v_{n} .$ It cannot repeat edges or vertices, except for the initial and terminal vertex.

🔗

If it is clear which vertices we must use, we often just use the edges,

e_{1} e_{2} \dots e_{n},

to describe paths, circuits, walks, etc.

🔗

The trivial walk is just the single vertex

v .

This is also the trivial circuit.

🔗

Example 10.2.3. Paths and Circuits.

Consider the graph

G .

Figure 10.2.4. The graph $G$ for Example 10.2.3

For each list of vertices and edges, decide if it is a walk, trail, path, closed walk, circuit, simple circuit.

$v_{2} e_{2} v_{1} e_{5} v_{4} e_{6} v_{2} e_{2} v_{1}$

Answer.
$v_{2} e_{2} v_{1} e_{5} v_{4} e_{6} v_{2} e_{1} v_{1}$

Answer.
$v_{2} e_{2} v_{1} e_{5} v_{4} e_{6} v_{2}$

Answer.
$v_{2} e_{2} v_{1} e_{5} v_{4} e_{6} v_{2} e_{1} v_{1}$

Answer.
$v_{2} e_{2} v_{1} e_{1} v_{2} e_{3} v_{3} e_{4} v_{2}$

Answer.

Definition 10.2.5.

Two vertices,

v, w,

are connected if there is a walk from

v

w .

🔗

Definition 10.2.6.

A graph,

G,

is connected if given any two vertices

v, w,

there is a walk from

v

w .

🔗

Basically, a graph is connected if it is in one piece. Figure 10.2.4 is an example of a connected graph. The example in Figure 10.1.3 with the isolated vertex, is an example of a graph that is not connected.

🔗

We state several propositions in this section without proof. You are encouraged to sketch examples of graphs to try to verify the propositions for yourself.

🔗

Proposition 10.2.7.

G

is a connected graph then any two distinct vertices of

G

can be connected by a simple path.

🔗

Activity 10.2.1.

Draw several examples of connected graphs. Verify for yourself that if

G

is connected then any two distinct vertices of

G

can be connected by a simple path.

🔗

Proposition 10.2.8.

v

and

w

are part of a circuit in

G

and one edge is removed, then there still exists a path from

v

w

G .

🔗

Activity 10.2.2.

Draw several examples of graphs with a circuit. Verify for yourself that if

v

and

w

are part of a circuit and one edge is removed then there still exists a path from

v

w

G .

🔗

Proposition 10.2.9.

G

is a connected graph and contains a nontrivial circuit, then an edge of the circuit can be removed without disconnecting

G .

🔗

Activity 10.2.3.

Draw several examples of connected graphs containing a nontrivial circuit. Verify for yourself that if

G

is connected and contains a nontrivial circuit then an edge of the circuit can be removed without disconnecting

G .

🔗

Definition 10.2.10.

An Euler circuit for a graph

G

is a circuit that contains every vertex and every edge of

G .

🔗

An Euler circuit must start and end at the same vertex and include every vertex and every edge. It can repeat vertices, but it cannot repeat edges. If you look back at the Konigsberg bridge problem, you can see that to solve the bridge problem is to find an Euler circuit for the associated graph. Were you able to find such a circuit?

🔗

Example 10.2.11. Finding Euler Circuits.

Is it possible to find an Euler circuit for the graph in Figure 10.2.12?

Answer 1.

e_{1} e_{5} e_{2} e_{3} e_{6} e_{4} .

Is it possible to find an Euler circuit for the Konigsberg bridge graph in Figure 10.2.13?

Answer 2.

Activity 10.2.4.

Draw the complete bipartite graphs

K_{2, 3},

K_{2, 4},

K_{3, 3}

and

K_{4, 4} .

Determine if each of these graphs has an Euler circuit.

🔗

We want to decide when a graph has an Euler circuit. The following two theorems completely characterize when a graph has an Euler circuit.

🔗

Theorem 10.2.14.

If a graph has an Euler circuit, then every vertex has even degree.

🔗

Although we will not prove this formally, the basic idea is that to create an Euler circuit for each vertex you need to be able to arrive at the vertex along an edge and then leave the vertex along a different edge. In the case of the inital vertex, you need to be able to leave the vertex and then return.

🔗

Theorem 10.2.14 tells us that the Konigsberg bridge graph cannot have an Euler circuit since we have vertices of odd degree.

🔗

Theorem 10.2.15.

If every vertex of a nonempty graph has even degree and is connected, then the graph has an Euler circuit.

🔗

Theorem 10.2.15 tells us that the graph in Figure 10.2.12 has an Euler circuit since all vertices have even degree, and the graph is connected. The graph in Figure 10.1.3 does not have an Euler circuit since it is not connected (although every vertex has even degree).

🔗

Activity 10.2.5.

Verify Theorem 10.2.14 and Theorem 10.2.15 on

K_{2, 3},

K_{2, 4},

K_{3, 3}

and

K_{4, 4} .

🔗

Definition 10.2.16.

An Euler path from

v

w

is a sequence of adjacent edges and vertices that starts at

v

and ends at

w

passing through every vertex of

G

at least once and traversing every edge exactly once.

🔗

An Euler path is a path that covers every edge and vertex of

G

without repeating edges.

🔗

Corollary 10.2.17.

A graph

G

has an Euler path from

v

w

if and only if

G

is connected,

v

and

w

have odd degree, and all other vertices of

G

have even degree.

🔗

Activity 10.2.6.

Draw a graph that has an Euler path but not an Euler circuit.

🔗

We’ve been focusing on traversing a graph by covering each edge exactly once, but what if we want to traverse each vertex exactly once?

🔗

Definition 10.2.18.

A Hamiltonian circuit for

G

is a simple circuit that includes every vertex of

G .

🔗

A Hamiltonian circuit starts and ends at the same vertex, passes through all other vertices without repeating, does not repeat edges, but does not need to use all the edges. For example, in the Konigsberg bridge graph Figure 10.2.13, we have Hamiltonian circuit