Proof
(related to Theorem: Characterization of Eulerian Graphs)
"\(\Rightarrow\)"
- Assume, a simple graph \(G(V,E)\) is Eulerian.
- Then there is an Eulerian tour.
- Whenever this trail passes through a vertex, there is a contribution of \(2\) to the degree of that vertex.
- Since each edge is used exactly once, the degree of each vertex is even.
- In particular, \(G\) is connected, since every vertex is connected to any other by a path.
"\(\Leftarrow\)"
- Assume, \(G\) is connected, and every one of its vertices has an even degree.
- We know from the lemma about splitting a graph with even degree vertices into cycles that \(G\) can be split into cycles \(C_1, C_2, C_3,\ldots\), no two of which have an edge in common.
- Fit these cycles to make an Eulerian tour as follows:
- Start at any vertex of \(C_1\) and travel round \(C_1\) until we meet a vertex of another cycle. Without any loss of generality, let it be \(C_2\) (otherwise re-label the cycles obtained in the order provided by the above lemma).
- Travel the edges of \(C_2\), and then resume traveling round \(C_1\).
- This gives a closed trail that includes \(C_1\) and \(C_2\).
- If this trail includes all the edges of \(G\), then we have found the required Eulerian tour.
- Otherwise, travel around our new closed trail, and add a new cycle, say \(C_3\).
- Continue this process, until you have traversed enough cycles to include all the edges of \(G\). At the worst case, we will need all the cycles constructed in the above lemma.
- It follows that \(G\) is Eulerian.
∎
Thank you to the contributors under CC BY-SA 4.0!
- Github:
-
References
Bibliography
- Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000