Euler Path Finder

Pseudocode

The existence test is pure counting and takes one pass. Only if it succeeds do you build the trail, using Hierholzer rather than naive backtracking.

// Existence, undirected connected graph:
//   0 odd-degree vertices -> Eulerian circuit
//   2 odd-degree vertices -> Eulerian path between them
//   anything else         -> neither

Hierholzer(graph, start):
    stack = [start]; trail = []

    while stack is not empty:
        u = stack.top
        if u has an unused incident edge (u,v):
            mark that edge used
            stack.push(v)
        else:
            trail.append(stack.pop())

    reverse(trail)

Hierholzer works because it never has to guess. It walks until it gets stuck, which on an all-even-degree graph can only happen back at the start, then splices in detours from vertices that still have unused edges. Every vertex is entered and left the same number of times, which is exactly what even degree guarantees, so the pieces always merge into one closed trail.

Worked example, step by step

Build an Eulerian circuit on two triangles that share a single vertex, taking neighbours in alphabetical order.

Example graph: Undirected edges A-B, B-C, C-A forming one triangle, and C-D, D-E, E-C forming a second, joined at C.

1. Check degrees first. A has degree 2, B has 2, C has 4, D has 2, E has 2. Every degree is even and the graph is connected, so an Eulerian circuit exists and it can start anywhere.
2. Walk until stuck. From A take A-B, then B-C, then from C take C-A. Now back at A with both of its edges used, so the walk is stuck. Note it got stuck at the start vertex, which even degrees make inevitable.
3. Splice in the second triangle. Unwinding the stack reaches C, which still has unused edges C-D and C-E. Walk C-D, then D-E, then E-C, and now C is exhausted too.
4. Unwind to the trail. With no unused edges anywhere, the stack pops in order and the reversed result is the circuit.

The Eulerian circuit is A to B to C to D to E to C to A, using all six edges exactly once and returning to the start. Note that C appears twice in the trail, which is allowed and expected: an Eulerian trail may revisit vertices freely, it may only not reuse an edge. That is the whole difference from a Hamiltonian path, which visits every vertex once and does not care about edges.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V + E)

The degree count is one pass over the edges at O(E), and the connectivity check is one traversal at O(V + E). Hierholzer then pushes and pops each vertex occurrence once and marks each edge used exactly once, so it is O(E) provided each vertex keeps a pointer into its adjacency list rather than rescanning from the beginning. Without that pointer the inner search degrades to O(V·E). Space is the used-edge marks plus the stack and trail, which hold O(E) entries. The contrast with Hamiltonian paths is worth noting: Eulerian is linear, Hamiltonian is NP-complete, purely because edges can be counted locally by degree while vertices cannot.

When to use Eulerian Path (Undirected), and when not to

Eulerian problems are easy; the superficially similar Hamiltonian ones are not. Check which you actually have.

Common pitfalls

• Forgetting the connectivity requirement. Even degrees alone are not enough. A graph made of two disjoint triangles has every degree even and no Eulerian circuit, because no trail can jump between components. All edges must lie in one connected component, and isolated vertices with degree zero are fine to ignore.
• Confusing Eulerian with Hamiltonian. Eulerian uses every edge once and may repeat vertices; Hamiltonian visits every vertex once and may skip edges. They sound alike and have wildly different difficulty: linear versus NP-complete.
• Rescanning adjacency lists in Hierholzer. If the search for an unused edge starts from the beginning of a vertex list each time, the algorithm becomes quadratic. Keep a per-vertex iterator that only advances, since an edge once used is never useful again.
• Applying the undirected degree rule to a directed graph. Directed graphs need in-degree to equal out-degree at every vertex for a circuit, or exactly one vertex with out minus in equal to 1 and one with in minus out equal to 1 for a path. Counting total degree gives the wrong answer.
• Starting a path at the wrong vertex. When exactly two vertices have odd degree, the trail must begin at one of them and end at the other. Starting anywhere else means getting stuck with edges left over.

Frequently asked questions

What is an Eulerian path?

An Eulerian path is a trail that uses every edge of a graph exactly once. It may visit vertices more than once. If it also returns to its starting vertex it is called an Eulerian circuit. The idea comes from Euler solving the Seven Bridges of Konigsberg problem in 1736, which founded graph theory.

When does an Eulerian path exist?

In a connected undirected graph, an Eulerian circuit exists when every vertex has even degree, and an Eulerian path exists when exactly two vertices have odd degree, in which case the path must start at one and end at the other. Any other number of odd-degree vertices means neither exists. All edges must also lie in a single connected component.

What is the difference between Eulerian and Hamiltonian paths?

An Eulerian path uses every edge once and may revisit vertices; a Hamiltonian path visits every vertex once and may ignore edges. The difference in difficulty is dramatic: deciding whether an Eulerian path exists takes O(V + E) by counting degrees, while deciding the Hamiltonian question is NP-complete.

How does Hierholzer's algorithm work?

It walks along unused edges until it gets stuck, which on an even-degree graph can only happen at the start vertex. It then backtracks along the stack, and whenever it finds a vertex with unused edges it walks a new closed loop from there and splices it in. Popping the stack yields the full trail in reverse, and the whole run is O(E).

What is the time complexity of finding an Eulerian path?

O(V + E). Counting degrees is O(E), checking connectivity is one traversal, and Hierholzer marks each edge used exactly once. The key implementation detail is a per-vertex pointer into the adjacency list so unused-edge searches never rescan, which keeps it linear rather than quadratic.