How to prove $G$ is Eulerian

Question

We know that a Eulerian graph has vertices all are even. But how can we prove the sufficiency of it i.e. if a connected graph $G$ has vertices all are even, then how can we prove the graph $G$ is Eulerian.

Answer 1

HBM's comment here is exactly to the point. I will elaborate on it.

First observe that if we pick any vertex $g\in G$, and then follow any path from $g$, marking each edge as it is used, until we reach a vertex with no unmarked edges, we must be at $g$ again. For let $\def\I#1{\operatorname{in}(#1)}\I x$ by the number of times the path enters vertex $x$ and $\def\O#1{\operatorname{out}(#1)}\O x$ be the number of times the path leaves $x$ again. If we end at some vertex $h\ne g$, we have $\I h = \O h + 1$. But each entry and each exit marks one edge incident to $h$. So $\I h + \O h = 2\cdot\I h -1$ of $h$'s edges are marked. But $2\cdot\I h -1$ is odd and by hypothesis $h$ has even degree. So there is still an unmarked edge incident to $h$, contradicting our hypothesis that $h$ has no unmarked edges. On the other hand, if we end at $g$, then we have $\I g = \O g$ and there is no contradiction. So it is easy to find a cycle in $G$: pick any vertex $g$ and go from vertex to vertex until you finish again at $g$; you cannot get stuck.

Having found this cycle $C$, there are either no unmarked edges, in which case $C$ is itself an Eulerian cycle of $G$, or else there is some vertex $v$ of $C$ which is incident to an unmarked edge. (If there are unmarked edges, but none incident to vertices of $C$, then $G$ must be disconnected.) Then we can find another cycle $C'$ of $G$, containing only unmarked edges, starting and ending at $v$, the same way that we found $C$ itself. Then we can merge $C$ and $C'$ into a single cycle as follows: Say that $C$ was $g-g_1-g_2-\cdots-v-g_k-\cdots -g_n-g$ and $C'$ was $v-h_1-\cdots-h_n-v$. Then we can merge $C$ and $C'$ into the single cycle $g-g_1-g_2-\cdots-v-h_1-\cdots -h_n-v-g_k-\cdots-g_n-g$.

In this way we can repeatedly find a new cycle and then merge it into the older one, until there are no unmarked edges remaining. At that point we have a single cycle that traverses all the edges of $G$, and we are finished.