Proving that we can construct an Euler trail in an undirected graph G, iff G is connected and has exactly two vertices of odd degree.

Question

I'm having trouble proving the following:

If G is an undirected graph with no isolated vertices, then we can construct an Euler trail in G if and only if G is connected and has exactly two vertices of odd degree.

Answer 1

Suppose $G$ has a Euler trail, then $G$ is connected. And except the start and end vertices of the trail, all vertices are of even degree(as you go into an intermediate vertex and you leave it). Now, suppose $G$ is a connected graph with exactly 2 vertices of odd degree. Then start a trail from one of the vertex with odd degree(Now you can think of that vertex as a vertex of even degree), and as you go through the vertices along the trail, you can always leave a vertex if they have even degrees or the vertex you started your trail from. You can only get stuck when you visit the other vertex of odd degree. If you end up stuck and hasen't visit all edges yet, then there must be an edge not visited yet and that is connected to a vertex $v$ in your current trail. Then start from $v$ and make another trail that tries to visit all the un-visited edges, you can get stuck only at $v$ . After that, join this trail to the previous one. repeat this same process if there is edges not visited yet by the trail. So then at the end, that gives an Euler trail(It is called the Hierholzer's algorithm for finding Euler trail). Is this correct?

Answer 2

An alternative proof to show that any connected graph with all even-degree vertices except for two (say, $u,v$) has an Eulerian trail, using the fact that a connected graph with all even-degree vertices contains an Eulerian tour. The other direction follows fairly easily, as outlined by @mathnoob above.

Add in a new vertex $x$ which only has edges to the two odd-degree vertices $u$ and $v$. This new graph is connected, and only has even-degree vertices. It follows that it has an Eulerian tour. Start from $x$ and follow this Eulerian tour; since there are only two edges incident on $x$, these must be the first and last edges in the tour. Removing $x$ and these two edges then gives an Eulerian trail beginning at $u$ and ending at $v$ or vice versa.