Euler circuit criterion

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.