Eulerian Path: Visit Every Edge Once, Never Repeat

In 1736, Leonhard Euler looked at a map of Königsberg and asked whether a walker could cross all seven bridges exactly once and return home. He proved it was impossible. Along the way he invented graph theory. Not bad for a failed walk.

In 1873, Carl Hierholzer published the constructive algorithm that finds such a path when one exists, in linear time. Today it shows up as a flight itinerary reconstructor, a sequence assembler, and a password cracker on LeetCode. The Königsberg tourists never got their walk. You get a coding interview.

The mental model: an Eulerian path visits every edge in a graph exactly once. An Eulerian circuit does the same but ends where it started. Hierholzer's algorithm builds one in O(E) time using a single depth-first traversal where nodes are committed to the result only after all their edges are exhausted.

The Two Questions You Have to Answer First

An Eulerian path or circuit may not exist. The degree conditions below are exact. Violate any one and no path is possible. Check these before writing a single line of code. Your algorithm won't tell you it failed. It'll just wander.

Undirected graphs

An Eulerian circuit exists if and only if every vertex has even degree and the graph is connected (considering only vertices with non-zero degree).

An Eulerian path (not a circuit) exists if and only if exactly two vertices have odd degree. Those two vertices are the start and end.

Directed graphs

An Eulerian circuit exists if and only if every vertex has in_degree == out_degree and the graph is strongly connected.

An Eulerian path exists if and only if:

• At most one vertex has out_degree - in_degree == 1 (the start)
• At most one vertex has in_degree - out_degree == 1 (the end)
• Every other vertex has equal in and out degree
• The graph is weakly connected

If none of the vertices have unequal in/out degree, the path is also a circuit and you can start anywhere.

Directed: check degree balance
   A (out=2, in=1)  →  start candidate (out - in = 1)
   B (out=1, in=1)  →  balanced
   C (out=0, in=1)  →  end candidate (in - out = 1)

Undirected: count odd-degree vertices
   A (degree=3) → odd
   B (degree=2) → even
   C (degree=1) → odd
   Two odd-degree vertices → Eulerian path from A to C

Directed graph (right): green = start (out minus in = 1), amber = end (in minus out = 1), blue = balanced. Undirected (left): amber = odd degree, blue = even degree.

Hierholzer's Algorithm: Post-Order DFS on Edges

The obvious approach is greedy: follow any unvisited edge until you can't. This fails quietly. You'll walk into a dead-end sub-path, strand entire subgraphs behind you, and end up stuck at a node with no exits and several perfectly good edges sitting unreachable on the other side of the graph.

Hierholzer's fix is elegant. Instead of greedy, use post-order DFS on edges: traverse edges normally, but only add a node to the result when you have no more edges to follow from it. Then reverse the result.

Here is the step-by-step on a six-edge graph with nodes 0, 1, 2, 3:

Edges: 0→2, 0→1, 1→0, 2→3, 3→0, 0→3
Degree check: 0(out=3,in=2), 1(out=1,in=1), 2(out=1,in=1), 3(out=1,in=2)
Start: node 0 (out - in = 1)

Step  Stack              Result (building reversed)   Action
  1   [0]                []                           0 has edges, push 1 (smallest)
  2   [0, 1]             []                           1 has edge to 0, push 0
  3   [0, 1, 0]          []                           0 still has edges, push 2
  4   [0, 1, 0, 2]       []                           2 has edge to 3, push 3
  5   [0, 1, 0, 2, 3]    []                           3 has edge to 0, push 0
  6   [0, 1, 0, 2, 3, 0] []                           0 still has edge to 3, push 3
  7   [0,1,0,2,3,0,3]    []                           3 has no edges → pop, add to result
  8   [0, 1, 0, 2, 3, 0] [3]                          0 has no edges → pop, add
  9   [0, 1, 0, 2, 3]    [3, 0]                       3 has no edges → pop, add
 10   [0, 1, 0, 2]       [3, 0, 3]                    2 has no edges → pop, add
 11   [0, 1, 0]          [3, 0, 3, 2]                 0 has no edges → pop, add
 12   [0, 1]             [3, 0, 3, 2, 0]              1 has no edges → pop, add
 13   [0]                [3, 0, 3, 2, 0, 1]           0 has no edges → pop, add
 14   []                 [3, 0, 3, 2, 0, 1, 0]        stack empty

Reverse: [0, 1, 0, 2, 3, 0, 3]

Every edge used exactly once. The path visits 0→1, 1→0, 0→2, 2→3, 3→0, 0→3.

Stack grows as we explore edges. A node only commits to the result when it has no more outgoing edges. Step 14: stack is empty, result is reversed to give the final path.

Why this is correct

The key invariant: when a node is popped from the stack to the result, all of its outgoing edges have been consumed. This means its position in the path is fully determined.

Pay attention to how dead-ends are handled. You walk into a vertex with no exits. That vertex gets added to the result right now. You backtrack to the previous vertex and keep exploring its other edges. Eventually that vertex too exhausts its edges and gets added. The reversed collection is the Eulerian path because every node appears after all the nodes it connects to have already been placed.

The key insight you're waiting to feel: nodes with more edges to explore act as "parking spots." Hierholzer says don't commit to the result until you've fully worked the neighborhood. Greedy commits too eagerly. That's the entire difference.

The algorithm always terminates with all edges used because the degree conditions prevent permanent deadlocks at internal vertices. A balanced vertex (equal in/out degree) always has a way out whenever you enter it. The only vertices that can run out of exits are the designated end vertex (one fewer out-edge) or the start vertex once the circuit is complete.

Same 5-edge graph. Greedy goes 1→2→1 and traps itself at node 1 with edges 2→3→4→2 unreachable. Post-order DFS defers the 2→1 edge until after the 2→3→4→2 loop closes.

Complexity at a Glance

Each edge is pushed onto the stack exactly once and popped exactly once, giving O(E) DFS. The stack can grow as large as the longest non-repeating path before any backtrack, which is at most E elements. The result array holds V nodes.

If you need a specific ordering among equal-degree candidates (like lexicographically smallest, required by LC 332), you sort each adjacency list. Sort adjacency lists descending and pop from the back for O(1) per removal. Using a min-heap instead costs O(log E) per extraction but handles dynamic insertions if needed.

For undirected graphs, the same algorithm applies with one extra step: when you traverse edge (u, v), you must remove it from both graph[u] and graph[v]. The cleanest approach is to index each edge and track visited edges by index rather than by endpoint.

One Structure, Every Language

Each implementation finds an Eulerian path in a directed graph given a list of edges as integer pairs. All implementations except C keep adjacency lists sorted, so the result is lexicographically smallest when multiple valid paths exist. The C implementation uses an unordered linked list and does not guarantee lex order.

from collections import defaultdict

def find_eulerian_path(edges: list[tuple[int, int]]) -> list[int]:
    graph: dict[int, list[int]] = defaultdict(list)
    in_deg: dict[int, int] = defaultdict(int)
    out_deg: dict[int, int] = defaultdict(int)

    for u, v in edges:
        graph[u].append(v)
        out_deg[u] += 1
        in_deg[v] += 1

    # Sort descending so pop() (O(1)) returns the smallest neighbor
    for node in graph:
        graph[node].sort(reverse=True)

    # Start at the vertex with out - in = 1, or any vertex with edges
    start = next(iter(graph))
    for node in set(out_deg) | set(in_deg):
        if out_deg[node] - in_deg[node] == 1:
            start = node
            break

    stack = [start]
    path: list[int] = []

    while stack:
        node = stack[-1]
        if graph[node]:
            stack.append(graph[node].pop())
        else:
            path.append(stack.pop())

    return path[::-1]

Where This Pattern Shows Up

Any problem that requires traversing every edge exactly once is an Eulerian path problem. Here are the recurring forms it takes.

Routing and coverage. The Chinese Postman Problem asks for the shortest closed walk that traverses every edge at least once in an undirected graph. If all vertices have even degree you already have an Eulerian circuit. If some are odd, you add minimum-weight edges to make them even, then find the Eulerian circuit on the augmented graph.

Sequence reconstruction. Given a set of overlapping fragments (DNA reads, string overlaps), can you reassemble the original sequence? Each fragment is a directed edge. The sequence exists as an Eulerian path through the overlap graph.

De Bruijn sequences. The shortest string over alphabet of size k containing every possible substring of length n as a contiguous window is an Eulerian circuit in the de Bruijn graph of k^(n-1) nodes. LeetCode 753 (Cracking the Safe) is this problem in disguise.

Itinerary reconstruction. Given a set of flight tickets (directed edges), find an itinerary that uses all of them starting from a given airport. LeetCode 332.

Pair arrangement. Given pairs [a, b], arrange them so that the second element of each pair equals the first element of the next. LeetCode 2097.

Five Signals It's an Eulerian Path Problem

Spot any one of these and you're looking at an Eulerian path problem. The algorithm is identical every time. The hard part is always the reframe, not the code. If the underlying graph machinery feels shaky, depth-first search fundamentals and graph representation for interviews are worth a pass first.

1. "Use every [ticket / connection / pair / edge] exactly once." That's the problem statement. Also the definition of an Eulerian path. Same sentence, different font.

2. "Find a path / sequence that covers all [items]" where each item connects two things. The items are edges, not nodes.

3. "Shortest string containing every combination of length k." This is always de Bruijn, which is always an Eulerian circuit.

4. "Arrange pairs so that adjacent pairs share an endpoint." Each pair is a directed edge, and you want an Eulerian path through the pair graph.

5. The constraint block gives you a count of items, not a count of nodes. 10,000 tickets, 500 airports. When there are 20x more items than locations, those items are almost certainly edges.

The hardest part is the reframe: recognizing that the abstract objects in the problem are edges, not nodes.

Neither problem mentions "graph" or "Eulerian." The reframe is invisible until it clicks. After that it's obvious.

Worked example 1: LC 332 Reconstruct Itinerary

Problem: Given a list of airline tickets as [from, to] pairs, reconstruct the itinerary starting from "JFK". Use all tickets. If multiple valid itineraries exist, return the lexicographically smallest one.

Why Eulerian path: Each ticket is a directed edge. Each airport is a node. Using all tickets exactly once is the definition of an Eulerian path. The start node is "JFK".

Degree check: The problem guarantees a valid itinerary exists, so degree conditions are already satisfied. JFK either has out - in = 1 or all degrees are balanced. Either way, start there.

Lexicographic smallest: Sort each airport's destination list. Post-order DFS naturally produces the lex-smallest path because we always pick the smallest available destination at each step.

from collections import defaultdict

def findItinerary(tickets):
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)

    # Equivalent: build graph then sort each list descending
    stack = ["JFK"]
    path = []

    while stack:
        airport = stack[-1]
        if graph[airport]:
            stack.append(graph[airport].pop())
        else:
            path.append(stack.pop())

    return path[::-1]

The sorted(tickets, reverse=True) trick pre-sorts all destinations in descending order before appending, so pop() always yields the lexicographically smallest destination. Time: O(E log E) for sorting. Space: O(E).

Worked example 2: LC 2097 Valid Arrangement of Pairs

Problem: Given pairs[i] = [start_i, end_i], rearrange them so that for consecutive pairs, end_i == start_{i+1}.

Why Eulerian path: Each pair [a, b] is a directed edge from a to b. The arrangement you're building is a sequence of edges where each edge's head matches the next edge's tail. That is an Eulerian path through the directed graph where the pairs are edges.

Start node: Find the vertex with out_degree - in_degree = 1. If none, all degrees are balanced and any vertex works.

Recovering the pair arrangement: The Eulerian path gives a sequence of nodes [v0, v1, v2, ..., vn]. The pairs in order are [[v0,v1], [v1,v2], ..., [v_{n-1},vn]].

from collections import defaultdict

def validArrangement(pairs):
    graph = defaultdict(list)
    in_deg = defaultdict(int)
    out_deg = defaultdict(int)

    for u, v in pairs:
        graph[u].append(v)
        out_deg[u] += 1
        in_deg[v] += 1

    start = pairs[0][0]
    for node in graph:
        if out_deg[node] - in_deg[node] == 1:
            start = node
            break

    stack = [start]
    path = []

    while stack:
        node = stack[-1]
        if graph[node]:
            stack.append(graph[node].pop())
        else:
            path.append(stack.pop())

    path.reverse()
    return [[path[i], path[i + 1]] for i in range(len(path) - 1)]

The problem says nothing about graphs or Euler. It describes a constraint on adjacent pairs that is structurally identical to the Eulerian path condition. The reframe is the entire difficulty. The code is just Hierholzer.

Quick Reference

• Eulerian circuit: all vertices have even degree (undirected) or equal in/out degree (directed), graph connected
• Eulerian path: exactly two odd-degree vertices (undirected) or exactly one vertex with out-in=1 and one with in-out=1 (directed)
• Algorithm: post-order DFS on edges, add node to result when edges exhausted, reverse
• Time: O(E) for the DFS; O(E log E) if adjacency lists are sorted
• Space: O(V + E) for the graph; stack holds at most O(E) nodes
• Start node: vertex with out-in=1 if it exists; otherwise any vertex with edges
• Key pattern signal: "use every [item] exactly once" where items connect two endpoints
• Common trap: treating the problem as a node-visit problem (Hamiltonian, NP-hard) rather than an edge-visit problem (Eulerian, O(E)). One of these appears in job interviews. The other is reserved for sadists.

If you want to practice recognizing this pattern and narrating the reframe under actual interview pressure, SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly these kinds of structural disguise problems. You get scored on how clearly you explain the graph model, not just whether the code compiles. Because in a real interview, "I'll run Hierholzer" means nothing if you can't first say "this is an Eulerian path problem because..."

Further Reading

• Eulerian path on Wikipedia, complete coverage of conditions, history, and variants
• Hierholzer's Algorithm on GeeksforGeeks, directed graph walkthrough with worked examples
• Finding the Eulerian path in O(M), cp-algorithms.com, competitive programming reference with formal conditions and implementation notes
• Seven Bridges of Königsberg on Wikipedia, the original problem that started graph theory
• NetworkX Euler algorithms documentation, canonical Python library reference for Eulerian path utilities