Eulerian Path, in depth: the degree conditions, the Hierholzer algorithm with an explicit stack, multigraphs, itineraries and de Bruijn sequences

The conditions, and why they are the right ones

Think about any vertex in the middle of a walk. Every time the walk arrives on one edge it must leave on another, so the edges at that vertex are used in pairs. Only the start and the end of the walk can break that pairing. That one observation gives every condition.

Two details are easy to get wrong. First, connectivity only covers vertices that have at least one edge. Isolated vertices are irrelevant; a graph with an unused vertex 7 can still have an Eulerian circuit. Second, for directed graphs you do not need strong connectivity as a separate test. If the degrees balance and the underlying undirected graph is connected, the walk can reach everything. Checking strong connectivity would wrongly reject valid path inputs, because in a path graph the end vertex need not reach the start.

The conditions are also sufficient, and the proof is the algorithm. Start at a legal start vertex and walk along unused edges until you cannot move. By the pairing argument you can only get stuck at the end vertex. If edges remain, some vertex on your walk still has unused edges, and those edges form closed loops, because removing your walk left every degree balanced. Splice each loop into the walk at the vertex where it touches, and repeat until none remain.

From splicing loops to an explicit stack

Naively, splicing means finding a vertex with leftover edges, walking a loop from it and inserting the loop into a linked list. Hierholzer's insight is that a stack does the bookkeeping for you. Keep the current walk on a stack. While the top vertex has an unused edge, follow it and push the next vertex. When the top vertex has none, pop it and append it to the output. The output, reversed, is the Eulerian path.

Why does that work? A vertex is popped only when all its edges are used, which means everything reachable from it in the remaining graph has already been emitted. Emitting in pop order produces the path from the end backwards; any loop discovered at a vertex lower in the stack is walked and emitted before that vertex is popped, which is exactly a splice at that position.

Reversed, the output is A, B, A, C, D, C, which uses A to B, B to A, A to C, C to D and D to C: all five edges once. A greedy walker that simply followed edges from A would have produced A, C, D, C and stopped with two edges unused.

Directed graphs: a tested implementation

The implementation keeps a pointer per vertex into its adjacency list, so each edge is examined once and the whole run is O(V + E). It uses an explicit stack because a recursive version recurses once per edge, which overflows Python's default limit at about a thousand edges and overflows native stacks on large graphs too.

def euler_directed(n, edges):
    """edges: list of (u, v) with 0 <= u, v < n. Returns a vertex list or None."""
    out = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        out[u].append(v)
        indeg[v] += 1

    start, plus, minus = None, 0, 0
    for x in range(n):
        d = len(out[x]) - indeg[x]
        if d == 1:
            plus, start = plus + 1, x
        elif d == -1:
            minus += 1
        elif d != 0:
            return None                      # imbalance of 2 or more
    if not (plus == minus == 0 or plus == minus == 1):
        return None
    if start is None:                        # circuit: start anywhere with an edge
        start = next((x for x in range(n) if out[x]), 0)

    ptr = [0] * n                            # next unused edge per vertex
    stack, path = [start], []
    while stack:
        u = stack[-1]
        if ptr[u] < len(out[u]):
            v = out[u][ptr[u]]
            ptr[u] += 1
            stack.append(v)
        else:
            path.append(stack.pop())
    path.reverse()
    # A disconnected edge set leaves edges unvisited: detect it here.
    return path if len(path) == len(edges) + 1 else None

Notice that there is no separate connectivity check. If the edges with nonzero degree fall into two components, the walk from start never reaches the second one, the result has fewer than E + 1 vertices, and the length test rejects it. That single comparison replaces a BFS and removes a whole class of bugs. The start choice matters: in the path case you must start at the +1 vertex, otherwise the walk can end prematurely and the length check will fail on a valid input.

Undirected multigraphs: mark edges, not vertex pairs

In an undirected graph each edge appears in two adjacency lists, so using it from one side must hide it from the other. The tempting shortcut is a set of used (u, v) pairs. That breaks on multigraphs, where two parallel edges between the same pair are different edges, and on self-loops, where both list entries live at the same vertex. Give every edge an id and mark the id.

def euler_undirected(n, edges):
    """edges: list of (u, v); parallel edges and self-loops allowed.
    Returns the edge ids in trail order, or None."""
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))                # a self-loop adds two entries at u
    odd = [x for x in range(n) if len(adj[x]) % 2]
    if len(odd) not in (0, 2):
        return None
    start = odd[0] if odd else next((x for x in range(n) if adj[x]), 0)

    used = [False] * len(edges)
    ptr = [0] * n
    stack, trail = [(start, -1)], []         # (vertex, edge id used to arrive)
    while stack:
        u, via = stack[-1]
        while ptr[u] < len(adj[u]) and used[adj[u][ptr[u]][1]]:
            ptr[u] += 1                      # skip edges consumed from the other end
        if ptr[u] == len(adj[u]):
            stack.pop()
            if via >= 0:
                trail.append(via)
        else:
            v, i = adj[u][ptr[u]]
            used[i] = True
            stack.append((v, i))
    trail.reverse()
    return trail if len(trail) == len(edges) else None

Returning edge ids rather than vertices is deliberate. With parallel edges a vertex sequence is ambiguous, and callers such as a route planner usually need to know which physical road segment was used. The skip loop keeps the total work linear: each adjacency entry is passed over at most once.

The itinerary problem and the smallest valid order

A common interview and production variant: given flight tickets as (from, to) pairs, all starting from JFK, reconstruct the itinerary that uses every ticket, choosing the alphabetically smallest when several are valid. Tickets are directed edges; the itinerary is an Eulerian path.

from collections import defaultdict

def itinerary(tickets, origin="JFK"):
    graph = defaultdict(list)
    for a, b in sorted(tickets, reverse=True):
        graph[a].append(b)                   # reverse-sorted so pop() yields the smallest
    stack, route = [origin], []
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        route.append(stack.pop())
    return route[::-1]

# itinerary([["JFK","KUL"], ["JFK","NRT"], ["NRT","JFK"]])
# -> ['JFK', 'NRT', 'JFK', 'KUL']

Greedy smallest-first alone fails on that example: it flies JFK to KUL first and is stranded with two tickets left. Hierholzer fixes it for free. KUL dead-ends, so it is popped first and lands at the end of the route, and the NRT loop is spliced in ahead of it. Taking the smallest edge at each step is still correct, because the post-order puts every dead-end branch after the loops that must precede it.

De Bruijn sequences

A de Bruijn sequence B(k, n) is a cyclic string over k symbols in which every length-n string appears exactly once as a substring. For k = 2 and n = 3 it has length 8 and contains all eight 3-bit codes. They are used to test every input combination of a lock or keypad with the fewest presses, for position encoding in structured-light scanning and rotary encoders, and as the basis of the de Bruijn graphs used in short-read genome assembly.

The construction is an Eulerian circuit. Make one vertex per (n-1)-symbol string and one edge per n-symbol string, from its prefix to its suffix. Every vertex has k outgoing and k incoming edges, so the graph is balanced and connected, and the circuit visits every n-symbol string exactly once.

def de_bruijn(k, n):
    if n == 1:
        return list(range(k))
    m = k ** (n - 1)                         # vertices encode (n-1)-symbol strings
    edges = [(v, (v * k + s) % m) for v in range(m) for s in range(k)]
    path = euler_directed(m, edges)          # balanced, so this is a circuit
    return [v % k for v in path[1:]]         # last symbol of each vertex visited

# de_bruijn(2, 3) -> [0, 1, 0, 1, 1, 1, 0, 0]; cyclically it contains
# 000 001 010 011 100 101 110 111 exactly once each.

In genome assembly the same graph is built from k-mers of sequencing reads. Real data is messier: sequencing errors add spurious edges, repeats make many circuits valid, and coverage gaps disconnect the graph, so assemblers clean the graph and emit unambiguous stretches (contigs) rather than one circuit. The Eulerian view is still why the de Bruijn approach scales where the Hamiltonian overlap-graph formulation does not.

Fleury, Hierholzer and related problems

Fleury needs bridge detection, which is covered in Bridges and Articulation Points. If you only need to know whether an Eulerian path exists, the degree test plus connectivity is enough, and connectivity can come from one BFS or DFS or from Union-Find while you read the edges. For directed graphs where reachability in both directions matters for other reasons, see Tarjan SCC.

Bugs that break real implementations

• Starting at the wrong vertex. For a path, start at the odd-degree vertex (undirected) or the +1 vertex (directed). Starting elsewhere yields a too-short result.
• Checking strong connectivity for directed paths. It rejects valid inputs.
• Counting isolated vertices in the connectivity test. It rejects valid inputs.
• Marking (u, v) pairs as used. It drops parallel edges and mishandles self-loops.
• Recursion. Depth equals edge count; use the explicit stack.
• Forgetting to reverse. The pop order is the path backwards.
• Rescanning adjacency lists. Without per-vertex pointers the algorithm becomes quadratic on high-degree vertices.
• Trusting the answer without the length check. It is the cheapest proof that every edge was used.

What to do next

1. Write the degree test for both graph types and run it on five small graphs you draw by hand.
2. Implement the directed version with the explicit stack and the E + 1 length check.
3. Trace the A, B, C, D example on paper until the splice makes sense, then trace one of your own.
4. Implement the undirected version with edge ids and test it with a parallel edge and a self-loop.
5. Solve the itinerary problem and confirm that greedy-only fails on the KUL example.
6. Generate B(2, 4) and verify all sixteen 4-bit strings appear once cyclically.
7. Add property tests: random balanced graphs must succeed, and every returned trail must use each edge id exactly once.
8. Read the Chinese postman problem to see what to do when the degree test fails but every edge must still be covered.