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.
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 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.
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.
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.
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{.}\)
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{.}\)
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?
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.
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.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).
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.
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.
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{.}\)
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.
