# 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

1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000