= Euler circuit criterion
{c}
Let $G=(V,E)$ be a finite undirected <multigraph>, allowing <self-loops> and distinct parallel <edges>, with $E\ne\varnothing$. Then
$$
G\text{ has an Euler circuit}\quad\Longleftrightarrow\quad G_+\text{ is connected and }\deg(v)\equiv0\pmod2\text{ for every }v\in V,
$$
where $G_+$ is the <edge support of a graph>, and <vertex degrees> count each <self-loop> twice. There is no lower bound of three on the number of <vertices>. If $E=\varnothing$, the zero-length convention gives an <Euler circuit> exactly when $V\ne\varnothing$.<Math 530: Graph Theory (Combinatorial Mathematics I), Spring 2023/Math 530 Spring 2023, Lecture 6: Multigraphs and digraphs>[p. 1, Theorem 1.1.2(a) and isolated-vertex note; p. 2, trivial trail convention]{ref}
The two requirements are independent: two separate <vertices>, each carrying a <self-loop>, have even <vertex degrees> but disconnected <edge support of a graph>, so no <Euler circuit> can cover both <edges>.
Necessity follows because a single <trail> cannot cover <edges> in different <connected components of a graph>, while a closed <trail> pairs all arriving and departing incidences, including those at its starting <vertex>. For sufficiency, extend a <trail> using unused <edges> until no extension is possible. Even <vertex degree> <parity> prevents it from stopping anywhere except its starting <vertex>: a different stopping <vertex> would have an odd number of used incidences and hence at least one unused incidence. The result is a closed <trail>.
If unused <edges> remain, connectivity of the <edge support of a graph> supplies a <vertex> on the current closed <trail> with an unused incident <edge>. Removing a closed <trail> leaves even unused <vertex degrees>, so the same argument constructs another closed <trail> from that <vertex>. Splice it into the existing record. The two <trails> use disjoint <edge> identities, so the splice repeats no <edge>. Each splice uses more <edges>; finiteness ensures termination with an <Euler circuit>. This is the constructive idea of <Hierholzer's algorithm>.
\Image[/hierholzer-closed-trail-splicing.png]
{title=<Hierholzer's algorithm> inserts one closed <trail> into another at their shared <vertex>, using each of six <edges> exactly once}
In the drawing, arrows indicate the chosen traversal direction along undirected <edges>. The first closed <trail> uses $AB,BC,CA$ and the second uses $AD,DE,EA$. Insert the second at the final occurrence of $A$ in $A,B,C,A$, giving $A,B,C,A,D,E,A$. A reader can check consecutive endpoints, closure, and the six distinct <edges> directly. With <multigraphs>, perform the same check on <edge> identities, since endpoint pairs alone cannot distinguish parallel <edges>.
Back to article page
