Eulerian Trail proof in Walk Through Combinatorics

Question

I'm struggling with the proof of Eulerian trail in walk through combinatorics. As you now, the theorem states that "A connected graph G has a closed Eulerian trail if and only if all vertices of G have even degree."

I'll only ask <- part. Book gives an algorithm how to construct an Eulerian trail actually.

1. Step: Take any vertex S, and start walking along an edge e1, to the other endpoint A1 of that edge, then walk along any new edge e2 that starts in A1. Continue this way, using new (previously unused) edges at each step, until a closed trail C1 is formed. The first closed trail will be formed when we first revisit a vertex already visited.

2. Step: If C1 = G, then we are done. If not, then choose a vertex V in C1 so that C1 does not contain all edges adjacent to V.

3. Step: Let us now remove all edges of C1 from G. We get a graph in which again all vertices have even degree. Starting at V , let us take another closed trail C2 in the remaining graph. We can then unite C1 and C2 into one closed trail in G. Indeed, if we start walking by C1, we can stop at V , walk through C2, then complete our trail by using the remaining part of C1.

Now my question is that in the algorithm when we start constructing our first C1 it does not guarantee that C1 includes the starting point S. Now again for C2 it does not actually guarantee that it includes vertex V. Then how can we union C1 and C2 ?

Answer 1

Indeed, the given description of the algorithm is slightly inaccurate. There are several ways to fix it. The easiest one is, in the first step, to continue as long as you can, i.e., until you arrive at a vertex and find out that all incident edges are used. At any moment of the procedure, we see by induction that for any vertex $W\neq S$, the following holds true: we have used an odd (respectively, even) number of edges incident to $W$ if we are currently at $W$ (respectively, not at $W$). Therefore, the process can only terminate at $S$.

Alternatively, you can frame is as a proof by induction on the number of edges in the graph. That way, after you remove a loop, the induction hypothesis guarantees that every connected component of $G$ with edges of $C_1$ removed not only has a loop, but a loop passing through all edges exactly once (hence through all vertices).