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.
Figure10.2.1.Konigsberg bridge problem, \(G\)
Definition10.2.2.
For each of the following terms we have a list of vertices and edges, \(v_0e_1v_1e_2\cdots e_nv_v\text{,}\) that represent a way to traverse through the graph. So, for example, \(v_0\) must be an endpoint of \(e_1\text{,}\)\(v_1\) must be an endpoint of \(e_1\) and \(e_2\text{,}\) 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\text{.}\) 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\text{.}\) 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\text{.}\) 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\text{,}\)\(v=v_0, v=v_n\text{.}\) It can repeat edges and vertices.
A circuit must start and end at the same vertex \(v\text{,}\)\(v=v_0, v=v_n\text{.}\) It cannot repeat edges. It can repeat vertices.
A simple circuit must start and end at the same vertex \(v\text{,}\)\(v=v_0, v=v_n\text{.}\) 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_1e_2\cdots e_n\text{,}\) to describe paths, circuits, walks, etc.
The trivial walk is just the single vertex \(v\text{.}\) This is also the trivial circuit.
For each list of vertices and edges, decide if it is a walk, trail, path, closed walk, circuit, simple circuit.
\(\displaystyle v_2e_2v_1e_5v_4e_6v_2e_2v_1\)
Answer.
walk
\(\displaystyle v_2e_2v_1e_5v_4e_6v_2e_1v_1\)
Answer.
walk, trail
\(\displaystyle v_2e_2v_1e_5v_4e_6v_2\)
Answer.
walk, trail, closed walk, circuit, simple circuit
\(\displaystyle v_2e_2v_1e_5v_4e_6v_2e_1v_1\)
Answer.
walk, trail
\(\displaystyle v_2e_2v_1e_1v_2e_3v_3e_4v_2\)
Answer.
walk, trail, closed walk, circuit
Definition10.2.5.
Two vertices, \(v, w\text{,}\) are connected if there is a walk from \(v\) to \(w\text{.}\)
Definition10.2.6.
A graph, \(G\text{,}\) is connected if given any two vertices \(v, w\text{,}\) there is a walk from \(v\) to \(w\text{.}\)
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.
Proposition10.2.7.
If \(G\) is a connected graph then any two distinct vertices of \(G\) can be connected by a simple path.
Activity10.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.
Proposition10.2.8.
If \(v\) and \(w\) are part of a circuit in \(G\) and one edge is removed, then there still exists a path from \(v\) to \(w\) in \(G\text{.}\)
Activity10.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\) to \(w\) in \(G\text{.}\)
Proposition10.2.9.
If \(G\) is a connected graph and contains a nontrivial circuit, then an edge of the circuit can be removed without disconnecting \(G\text{.}\)
Activity10.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\text{.}\)
Definition10.2.10.
An Euler circuit for a graph \(G\) is a circuit that contains every vertex and every edge of \(G\text{.}\)
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?
Example10.2.11.Finding Euler Circuits.
Is it possible to find an Euler circuit for the graph in Figure 10.2.12?
Figure10.2.12.Answer1.
Yes. For example \(e_1e_5e_2e_3e_6e_4\text{.}\)
Is it possible to find an Euler circuit for the Konigsberg bridge graph in Figure 10.2.13?
Figure10.2.13.Answer2.
No.
Activity10.2.4.
Draw the complete bipartite graphs \(K_{2, 3}\text{,}\)\(K_{2, 4}\text{,}\)\(K_{3, 3}\) and \(K_{4, 4}\text{.}\) 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.
Theorem10.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.
Theorem10.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).
Activity10.2.5.
Verify Theorem 10.2.14 and Theorem 10.2.15 on \(K_{2, 3}\text{,}\)\(K_{2, 4}\text{,}\)\(K_{3, 3}\) and \(K_{4, 4}\text{.}\)
Definition10.2.16.
An Euler path from \(v\) to \(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.
Corollary10.2.17.
A graph \(G\) has an Euler path from \(v\) to \(w\) if and only if \(G\) is connected, \(v\) and \(w\) have odd degree, and all other vertices of \(G\) have even degree.
Activity10.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?
Definition10.2.18.
A Hamiltonian circuit for \(G\) is a simple circuit that includes every vertex of \(G\text{.}\)
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 \(v_1e_5v_4e_7v_3e_3v_2e_1v_1\text{.}\)
Activity10.2.7.
Draw the complete bipartite graphs \(K_{2, 3}\text{,}\)\(K_{2, 4}\text{,}\)\(K_{3, 3}\) and \(K_{4, 4}\text{.}\) Determine if these graphs have an Hamiltonian circuit.
Reading QuestionsCheck Your Understanding
Use the following graph for questions about \(G\text{.}\)
Figure10.2.19.The graph \(G\) for Check Your Understanding
1.
True or false: \(v_1e_2v_3e_5v_2e_7v_2\) is a path in \(G\text{,}\)Figure 10.2.19.
True.
It repeats \(v_2\text{.}\)
False.
It repeats \(v_2\text{.}\)
2.
True or false: \(v_1e_2v_3e_5v_2e_7v_2\) is a closed walk in \(G\text{,}\)Figure 10.2.19.
True.
It starts and ends at different vertices.
False.
It starts and ends at different vertices.
3.
True or false: \(v_1e_2v_3e_5v_2e_7v_2e_1v_1\) is a circuit in \(G\text{,}\)Figure 10.2.19.
True.
False.
4.
True or false: \(v_1e_2v_3e_5v_2e_7v_2e_1v_1\) is a simple circuit in \(G\text{,}\)Figure 10.2.19.
True.
It repeats \(v_2\text{.}\)
False.
It repeats \(v_2\text{.}\)
5.
True or false \(v_4e_3v_2e_6v_4\) is a simple circuit in \(G\text{,}\)Figure 10.2.19.
True.
False.
6.
True or false: \(G\text{,}\)Figure 10.2.19, has an Euler circuit.
True.
There are vertices of odd degree.
False.
There are vertices of odd degree.
7.
True or false: \(G\text{,}\)Figure 10.2.19, has an Euler path.
True.
A path can start at \(v_1\text{,}\) end at \(v_4\text{.}\)
False.
A path can start at \(v_1\text{,}\) end at \(v_4\text{.}\)
8.
True or false: \(G\text{,}\)Figure 10.2.19, has a Hamiltonian circuit.
True.
For example, \(e_2e_5e_6e_4\text{.}\)
False.
For example, \(e_2e_5e_6e_4\text{.}\)
ExercisesExercises
1.
In the graph below, determine whether the following walks are trails, paths, closed walks, circuits, simple circuits, or just walks.
