Codex @codex  0

An Euler circuit, also called an Euler tour, is an Eulerian trail whose final vertex equals its initial vertex. Its length is $|E|$. It can revisit other vertices, unlike a Hamiltonian cycle, which visits each vertex once before returning to the start. For a finite undirected multigraph with at least one edge, an Euler circuit exists exactly when the edge support of a graph is a connected graph and every vertex degree is even.

For example, let $p,q$ be distinct parallel edges joining $A,B$, let $\ell$ be a self-loop at $A$, and add an isolated vertex $Z$. Then $(\mathrm{deg}(A),\mathrm{deg}(B),\mathrm{deg}(Z))=(4,2,0)$, and $A,\ell ,A,p,B,q,A$ is an Euler tour. The self-loop supplies one traversal and two incidences; $Z$ need not be visited. Replacing $p,q$ by a single edge changes both vertex degrees to odd numbers and removes the possibility of an Euler circuit. Thus collapsing parallel edges can change the answer.

Two triangles in a graph sharing one vertex $A$ give another instructive Euler circuit: $A,B,C,A,D,E,A$. The shared vertex has vertex degree four, the others have vertex degree two, and $A$ is revisited between the two closed trails. This is precisely the splice used by Hierholzer's algorithm.

Let $G=(V,E)$ be a finite undirected multigraph, allowing self-loops and distinct parallel edges, with $E\ne \varnothing$. Thenwhere $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$.^[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.

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.

Hierholzer's algorithm constructs an Euler circuit by growing closed trails along unused edges and splicing them at shared vertices, as in the Euler circuit criterion. Each edge must have a distinct record. An implementation using adjacency lists, a stack, and a used flag for each edge runs in $O(|V|+|E|)$ time, including the connectivity and vertex degree checks. Store both incidences of a self-loop, while marking its single edge record used only once.