We first show that if
\(G\) is Eulerian, then every vertex has even degree and the graph is connected. We know that if
\(G\) contains a circuit traversing every edge, then it must be connected. To show even degree, suppose that we have an Eulerian circuit
\(C\text{,}\) which passes through every edge exactly once. We will start at an initial vertex
\(v_0\) and we will follow
\(C\text{,}\) adding to the degree of each vertex whenever we pass through an edge adjacent to it. When
\(C\) first departs from
\(v_0\text{,}\) we add one to the degree of
\(v_0\text{.}\) Every time we pass through a vertex while traversing
\(C\text{,}\) we add two to the degree of that vertex. When we return to
\(v_0\) for the final time to end the circuit, we add one more to the degree of
\(v_0\text{.}\) Thus, the degree of every vertex is a sum of
\(2\)’s, and hence every vertex has even degree.
Second, we will show that if every vertex in
\(G\) has even degree and
\(G\) is connected, then the graph is Eulerian. We will give a proof that is a recursive algorithm. Pick any vertex
\(v\) of
\(G\) and begin to randomly create a path through the graph, never using the same edge twice. Stop when you return to a vertex
\(v_1\) that you have already passed through. It is impossible to become ``stuck’’ at a vertex during this random walk, because since the degree is even, if you arrive at a vertex along an edge, there is always another edge that you can depart along. The circuit that you create starting and ending at
\(v_1\) we will call
\(C_1\text{.}\) Remove the edges in
\(C_1\) from
\(G\text{,}\) leaving a graph
\(G_1\) which might consist of multiple connected components. Observe that since every vertex in
\(C_1\) has even degree, the graph
\(G_1\) has every vertex of even degree as well. Pick a vertex
\(v_2\) in
\(G_1\) and repeat this process, yielding a circuit
\(C_2\) and the graph
\(G_2\) obtained by removing the edges in
\(C_2\) from
\(G_1\text{.}\) Repeating this process, we obtain a sequence of Eulerian circuits
\(C_1\text{,}\) \(C_2\text{,}\) \(C_3\text{,...,}\) \(C_k\text{.}\) Note that this process must end because there are only finitely many edges in
\(G\text{.}\) Further, observe that the edge set of
\(G\) is the disjoint union of the edges in this sequence of circuits.
What remains is to combine the circuits into a single Eulerian circuit of
\(G\text{.}\) Start with
\(C_1\text{.}\) Since
\(G\) is connected, there must be a vertex
\(w\) of
\(C_1\) that is shared by another circuit
\(C_i\text{.}\) Cut each of
\(C_1\) and
\(C_i\) at
\(w\) and combine them to create one larger Eulerian circuit. Replace
\(C_1\) with this circuit and delete
\(C_i\) from our list. Continue this process until there is only one circuit left, and this produces an Eulerian circuit for
\(G\text{.}\)
