Section Project: Proof of Fleury's Theorem
As we will see in the next chapter, optimization problems often do not have a known and efficient solution that always works. Fleury's Theorem says that the Mail Carrier Problem is one of the exceptional ones that does.
Notice that Fleury's Algorithm can be applied to any graph whereas Fleury's Theorem applies only to special graphs. Assume we apply Fleury's Algorithm to some graph starting at some vertex \(A\text{.}\) Each time we traverse an edge we erase it, thereby ensuring that we will not traverse it more than once. Since the number of edges is finite, we must eventually stop at Step 4 because there is no edge we can traverse. Now, there are only three possible reasons why there would be no edge we could traverse.
-
R1..
We are at a degree 0 vertex, having erased all other vertices and all edges. In that case we have traversed all edges (exactly once) and have therefore found an Euler Path! :)
-
R2..
We are at a degree 0 vertex but there are remaining edges we have not traversed. In that case we can not extend our path to an Euler Path. :(
-
R3..
We are at a vertex of degree greater than one, but every edge connecting to it is a cut edge. In that case Step 2 prevents us from traversing any of these edges to complete an Euler Path. :(
We will prove Fleury's Theorem by showing that, under the conditions it imposes, neither R2 nor R3 will happen.
Definition 5.43.
A subgraph of a graph is a subset of the vertices of the graph along with the edges that connected them in the original graph.
Let \(\G\) be a connected graph and let \(e\) be a cut edge of \(\G\) connecting vertex \(A\) with vertex \(B\text{.}\) Let \(\X\) be the subgraph of \(\G\) made up of all vertices \(C\) such that there is a path from \(C\) to \(A\) that does not go over \(e\text{.}\) In particular, \(A\) is in \(\X\text{.}\) Let \(\Y\) be the subgraph made up of all of the remaining vertices.
Problem 5.44.
Show that a vertex \(D\) of \(\G\) is in \(\Y\) if and only if there is a path from \(D\) to \(B\) that does not go over \(e\text{.}\) In particular, \(B\) is in \(\Y\text{.}\)
Problem 5.45.
If \(e\) is a cut edge, the subgraphs \(\X\) and \(\Y\) are both connected.
Problem 5.46.
The subgraphs \(\X\) and \(\Y\) each contain an odd vertex.
Problem 5.47.
Assume Fleury's algorithm is applied to a connected graph. Then, for each non-negative integer \(n\text{,}\) the graph formed by the vertices and edges remaining after traversing \(n\) edges is connected.
Problem 5.48.
Show that, if Fleury's Algorithm is applied to a connected graph, then { R2} can not happen.
Up to now we have not mentioned the conditions Fleury's Theorem imposes on the number of odd vertices: there are either no odd vertices or exactly two odd vertices. We will need this hypothesis to show R3 can not happen either.
Problem 5.49.
Assume Fleury's Algorithm is applied to a connected graph with two odd vertices. Let \(P\) be the odd vertex where the path begins and let \(Q\) be the other odd vertex. Prove the following is true for each non-negative integer \(n\text{.}\) If the path traverses \(n\) edges, then either
we are at vertex \(Q\) and there are no odd vertices in the remaining graph or
we are not at vertex \(Q\) and there are exactly two odd vertices in the remaining graph: \(Q\) and the vertex we are at.
Problem 5.50.
Assume Fleury's Algorithm is applied to a connected graph with no odd vertices. Let \(Q\) be the vertex where the path begins. Prove the following is true for each non-negative integer \(n\text{.}\) If the path traverses \(n\) edges, then either
we are at vertex \(Q\) and there are no odd vertices in the remaining graph or
we are not at vertex \(Q\) and there are exactly two odd vertices in the remaining graph: \(Q\) and the vertex we are at.
Problem 5.51.
Use the facts you have established to explain why R3 can not happen when Fleury's Algorithm is applied to a connected graph with either no odd vertices or exactly two odd vertices. It follows that the path must end at Step 4 for reason R1, and therefore must be an Euler Path.