Eulerian Graphs and Circuits

Part 1, forward direction (necessity of even degree). Suppose $G$ has an Euler circuit $C = v_0, e_1, v_1, \dots, e_m, v_m$ with $v_0 = v_m$, using every edge of $E$ exactly once. Fix any vertex $u \in V$. Consider all occurrences of $u$ in the sequence $v_0, v_1, \dots, v_m$. If $u$ occurs at some interior position $v_i$ with $0 < i < m$, the circuit enters $u$ via edge $e_i$ and leaves via edge $e_{i+1}$; these are two distinct edges (a trail has distinct edges) both incident to $u$, and they are used up by this single visit. If $u = v_0 = v_m$ (the basepoint), the circuit leaves via $e_1$ at the start and enters via $e_m$ at the end; these too are two distinct edges incident to $u$ contributed by the "closing up" of the circuit. Every edge of $G$ appears exactly once in the list $e_1,\dots,e_m$, and each edge incident to $u$ is counted in exactly one of these visit-pairs (either as an "enter/leave" pair at an interior visit, or as the "leave-at-start/enter-at-end" pair if $u$ is the basepoint). Hence the edges incident to $u$ are partitioned into pairs, so their number — namely $\deg(u)$ — is even. (A loop at $u$ contributes $2$ to $\deg(u)$ by convention and corresponds to one traversal that both enters and leaves $u$, consistent with this pairing.) Since $u$ was arbitrary, every vertex has even degree.

Part 1, converse (sufficiency), by strong induction on $|E|$. Claim: if $G$ is connected, has at least one edge, and every vertex has even degree, then $G$ has an Euler circuit. Base case. If $|E| = 1$, connectivity with even degrees forces that single edge to be a loop at some vertex $v$ (a non-loop edge would give its two endpoints degree $1$, which is odd). The loop itself, traversed once, is an Euler circuit. Inductive step. Suppose $|E| = m \ge 2$ and the claim holds for all connected graphs with fewer than $m$ edges in which every vertex has even degree. Let $G$ satisfy the hypotheses with $|E| = m$. Step A: $G$ contains a closed trail. Since $G$ is connected with $\ge 2$ edges, some vertex has degree $\ge 2$; since all degrees are even, in fact every vertex of positive degree has degree $\ge 2$. Start at any vertex $v_0$ and build a trail greedily: having arrived at $v_i$ via an unused edge, if some incident edge at $v_i$ is unused, traverse it to $v_{i+1}$; repeat. Because degrees are all even, we argue this process cannot get stuck except by returning to $v_0$: suppose the trail reaches a vertex $u \ne v_0$. Each prior visit to $u$ (if any) used two of its incident edges (one in, one out); since $\deg(u)$ is even, the number of unused edges at $u$ is even after any number of full in/out pairs have been consumed, hence at least one unused edge remains if the count of used edges at $u$ has not reached $\deg(u)$, and in particular right after arriving we have used one more edge (the arriving one) than we have departing, so an even total forces at least one more unused edge to depart on. Thus the walk can always continue from any vertex other than possibly $v_0$. Since $G$ is finite, the process must terminate, and by the argument above it can only terminate by returning to $v_0$ with no more available edges there being unnecessary — indeed it terminates precisely when we return to $v_0$ (a vertex $\ne v_0$ never terminates the walk because an unused incident edge is always available there, as shown). This produces a closed trail $C_0$ based at $v_0$. Step B: remove $C_0$ and apply induction. Let $G' = G - E(C_0)$ be the graph on vertex set $V$ with edge set $E \setminus E(C_0)$ (deleting isolated vertices produced, if any, does not affect what follows). For every vertex $w$, the edges of $C_0$ incident to $w$ number an even amount (by the same pairing argument as in Part 1's forward direction, applied to the closed trail $C_0$), so

is even, being a difference of two even numbers. Thus every vertex of $G'$ has even degree. $G'$ may be disconnected; let $H_1, \dots, H_k$ be its connected components that contain at least one edge (components with no edges are single leftover vertices and are ignored, as they contribute nothing to traverse). Each $H_j$ is connected, has all-even degrees, and $|E(H_j)| < |E(G)| = m$ since $E(C_0) \ne \emptyset$ has been removed. By the induction hypothesis, each $H_j$ has an Euler circuit $C_j$. Step C: splice. Because $G$ is connected and $C_0$ together with $H_1,\dots,H_k$ covers all edges of $G$, each $H_j$ must share at least one vertex with $C_0$: if some $H_j$ shared no vertex with $C_0$, then since $H_j$ has at least one edge, there would be no path in $G$ from a vertex of $C_0$ to a vertex of $H_j$ that avoids... more directly, connectivity of $G$ guarantees a path from $v_0$ (on $C_0$) to any vertex of $H_j$; the first edge of this path leaving the vertex set of $C_0$ must belong either to $C_0$ (impossible, it would already be in $C_0$'s vertex set on both ends only if it's a $C_0$ edge) or to some component of $G'$ — tracing this path shows the path must pass through a vertex lying on both $C_0$ and $H_j$, since all edges of $G$ lie in $C_0$ or in some $H_i$ and a path cannot jump between disjoint vertex sets without an edge connecting them. Hence $C_0$ and $H_j$ share a vertex $u_j$. Now build the Euler circuit of $G$ by walking $C_0$ starting at $v_0$, and each time we arrive at a vertex $u_j$ that lies on some not-yet-inserted circuit $C_j$, we detour: traverse all of $C_j$ (starting and ending at $u_j$, since $C_j$ is a closed trail based there) before continuing along $C_0$. After all detours are spliced in, every edge of $C_0$ and every edge of every $C_j$ has been traversed exactly once, the walk starts and ends at $v_0$, and together these account for every edge of $E(C_0) \cup E(H_1) \cup \dots \cup E(H_k) = E$. This is an Euler circuit of $G$, completing the induction.

Part 2, forward direction. Suppose $G$ has an Euler trail $T: v_0, e_1, \dots, e_m, v_m$ with $v_0 \ne v_m$, using every edge exactly once. For any interior vertex $u$ (including possibly $v_0$ or $v_m$ if they recur mid-trail), each occurrence of $u$ strictly between the two endpoints pairs up two distinct incident edges exactly as in Part 1. For $v_0$: it contributes one unpaired "departure" edge $e_1$ at the very start, plus one paired in/out edge for each subsequent visit to $v_0$ (if any); hence $\deg(v_0)$ is odd (one unpaired edge, plus an even number from repeat visits). Symmetrically $\deg(v_m)$ is odd. Every other vertex $u \ne v_0, v_m$ has all its incident-edge occurrences paired as interior visits, so $\deg(u)$ is even. Thus $G$ has exactly two odd-degree vertices, namely $v_0$ and $v_m$.

Part 2, converse. Suppose $G$ is connected and has exactly two odd-degree vertices, $x$ and $y$. Form $G^+ = G + xy$ by adding one new edge between $x$ and $y$ (if $xy \in E$ already, add a parallel edge; this is permitted since $G$ may have multiple edges). In $G^+$, the degrees of $x$ and $y$ each increase by $1$, becoming even, and all other degrees are unchanged, hence even. Also $G^+$ is connected (adding an edge to a connected graph keeps it connected) and has at least one edge. By Part 1 (already proved), $G^+$ has an Euler circuit $C^+$. Since $xy$ is one edge of $C^+$, we may write $C^+$ starting immediately after traversing edge $xy$: that is, $C^+$ visits $x, y$ (or $y,x$) consecutively via edge $xy$ at some point; deleting that single edge occurrence from the circular sequence and "cutting" the circuit open there yields a trail from $y$ to $x$ (or $x$ to $y$) that uses every edge of $G^+$ except $xy$ exactly once — that is, every edge of $G$ exactly once. This is the desired Euler trail of $G$, and it runs between $x$ and $y$. Finally, we already showed (forward direction) that any Euler trail of a graph with exactly two odd vertices must start and end at those two odd vertices, so the endpoints are forced to be $\{x,y\}$ in either order. $\blacksquare$