An Eulerian circuit is a walk that crosses every edge of a graph exactly once and returns to where it started. Drop the "returns to start" requirement and it's an Eulerian path instead — every edge once, but the walk is allowed to end somewhere else. This is the question Leonhard Euler answered in 1736 for the Prussian city of Königsberg, whose seven bridges connected four landmasses — could a walker cross every bridge exactly once? Euler's answer, before graph theory even had a name, was the same test this page builds: every one of Königsberg's four landmasses touches an odd number of bridges, and that alone rules out any such walk, for a reason spelled out below.
Easy to confuse with Hamiltonian path / cycle, which asks the mirror-image question about vertices instead — visit every vertex exactly once, edges are just how you move between them. The two problems look like siblings but aren't: Hamiltonian path has no known efficient test and needs backtracking search even to decide whether an answer exists at all; Eulerian path has an exact one-line existence test and, when one exists, finding it takes linear time — no search, no guessing, no backtracking.
Five nodes, two triangles sharing C: A–B–C–A and C–D–E–C.
Every vertex has even degree, so an Eulerian circuit exists from anywhere. Press Step
or Run to watch Hierholzer's algorithm walk it with an explicit
stack: the top of the stack is outlined solid, the rest of the stack is dashed, and an edge turns
solid once it's been used. When the top of the stack runs out of unused edges, it's popped straight
into the assembled trail strip below — read right to left, since the algorithm
finishes the end of the trail before it finishes the middle. Toggle the checkbox to remove
edge A–B: that leaves exactly two odd-degree vertices, turning the graph from a circuit
into a path, and the degree strip below the graph marks the odd ones directly.
The existence test has two parts, and both matter. Degree parity: every time a walk passes through a vertex (not counting where it starts or ends), it uses one edge to arrive and a different edge to leave — edges get used up in pairs at every interior visit. That means every vertex touched by the walk needs an even number of its edges, except possibly the two endpoints, which can be odd because their very first or very last edge is unpaired. A circuit has no distinct endpoints (start and end are the same vertex, and even there the arriving-and-leaving pairing still holds), so a circuit demands zero odd-degree vertices; a path demands exactly the two endpoints be odd, so exactly two odd-degree vertices, or zero if it happens to close into a circuit too. Nothing else is allowed — the demo's Königsberg-inspired counting is that blunt. Connectivity: parity alone only checks each vertex in isolation, so it says nothing about whether the edges are even reachable from one another as a single piece — see Pitfalls below for a graph that passes the parity test at every vertex and still has no Eulerian anything.
Given that a trail exists, actually building one is where Hierholzer's algorithm earns its keep over the obvious approach. A single greedy walk — follow unused edges until stuck, stop — reliably gets stuck too early, stranding whole loops of untouched edges (also demonstrated in Pitfalls). Hierholzer's fix is to never really stop: keep the walk on an explicit stack, and the instant its top vertex runs dry of unused edges, don't abandon the walk — pop that vertex off and record it as finished, then keep working on whatever's still underneath. Because a vertex only truly runs dry once every one of its edges is used, and the walk always eventually returns to any vertex it still owes a visit to (that's exactly what the parity guarantee promises), every detour taken earlier gets spliced back in automatically, just recorded in reverse: the first vertex popped is the true last vertex of the finished trail, and the last vertex popped — the one that finally empties the stack — is the true first.
Matches the demo's own step generator exactly, minus the yields. edges
is a list of [a, b] pairs; the graph is undirected, so each edge is pushed into both
endpoints' adjacency lists tagged with a shared id, and used is checked by that id, not
by vertex, so a parallel edge between the same two vertices is never mistaken for one already
crossed.
function eulerianTrail(numNodes, edges, start) {
const adjacency = Array.from({ length: numNodes }, () => []);
edges.forEach(([a, b], id) => {
adjacency[a].push({ to: b, id });
adjacency[b].push({ to: a, id });
});
const ptr = new Array(numNodes).fill(0);
const used = new Array(edges.length).fill(false);
const stack = [start];
const trail = [];
while (stack.length > 0) {
const v = stack[stack.length - 1];
while (ptr[v] < adjacency[v].length && used[adjacency[v][ptr[v]].id]) ptr[v]++;
if (ptr[v] < adjacency[v].length) {
const { to, id } = adjacency[v][ptr[v]];
used[id] = true;
stack.push(to);
} else {
trail.push(stack.pop());
}
}
return trail.reverse(); // built end-to-start, see "Why it works"
}start has to be chosen correctly, not just conveniently: any vertex works when every
degree is even, but with exactly two odd-degree vertices it has to be one of those two — see the
third Pitfall for exactly what goes wrong otherwise.
A plain greedy walk gets stuck with edges still unused, even when a circuit
exists. Checked directly against the demo's own circuit graph: starting at A and
just following unused edges with no backtracking produces A–B–C–A — a clean-looking
closed loop, back at the start, using only 3 of the 6 edges. It stops there because
nothing forces it to notice that C still has two unused edges (to D and to
E) leading to an entire untouched second triangle. The walk isn't wrong, exactly — every
edge it used, it used once — it's just declared victory too early because closing a loop and being
finished look identical from inside a walk with no memory of what it's skipped. Hierholzer's stack
never makes this mistake: the same walk under the real algorithm still detects it's "stuck" at
C after the same three edges, but instead of stopping, it pops C, backtracks
onto whatever pushed it there, and keeps going — that's the entire reason the stack is there.
Even degree at every vertex still isn't enough — the edges have to be one connected
piece. Take two separate triangles, {A,B,C} and {D,E,F}, with no
edge between them at all. Every single vertex has degree 2, an even number, so the parity test passes
cleanly at all six of them — and yet no Eulerian circuit exists, because nothing connects the two
triangles for a single walk to cross between. Run the real algorithm on this graph starting at
A and it terminates having used exactly 3 of the 6 edges — all of
triangle {A,B,C}, none of {D,E,F} — and reports done, because from the
algorithm's point of view the stack legitimately emptied; it has no way to know a second component
exists unless something checks for it first. The fix isn't in Hierholzer's algorithm itself, which is
only ever asked to walk one component — it's a precondition check before calling it: every vertex with
a nonzero degree needs to be reachable from every other one.
With exactly two odd-degree vertices, starting anywhere else doesn't fail loudly — it
silently returns a corrupted trail. This is the sharpest one. Take the demo's graph with
A–B removed: A and B both drop to degree 1 (odd), so an
Eulerian path exists, and it has to start at A or B. Start the real
algorithm at C instead (even degree, the "wrong" choice) and it still runs to completion,
still reports using all 5 of 5 edges, and prints out
C–D–E–C–A–B — which looks like a complete answer right up until the last step, a
supposed edge from A to B that was removed from the graph before the
algorithm ever ran. Checked directly by validating that walk edge by edge against the actual edge
list: every hop up through C–A is real, and the final A–B hop is not.
What actually happened is the stack made two short dead-end side trips early on — out to
B and back, out to A and back — while sitting at C, before ever
starting the real C–D–E–C loop; each of those dead ends gets popped and recorded as if it
were adjacent to whatever gets popped next, and the reversal at the end stitches those unrelated
fragments together into one fluent-looking but fictitious walk. Nothing about the algorithm's own
bookkeeping — stack empty, every edge marked used — flags that anything went wrong; the corruption is
only visible by re-checking the output against the graph.
Time: O(V + E) — building the tagged adjacency lists is
O(V + E), and in the main loop each vertex's pointer only ever moves forward through its
own adjacency list, so the total work advancing every pointer across the whole run is bounded by the
sum of every adjacency list's length, O(E); every push and pop is O(1) and
there are at most E of each. Space: O(V + E) for the
adjacency lists, the used array, and the stack, which in the worst case (a graph that's
almost one long chain) holds close to every vertex at once.
This site's guide, Choosing a Graph Traversal Approach, compares this entry against the other ten Graph Traversal entries side by side.