Eulerian Paths and Circuits (Hierholzer's Algorithm)

This is an extension topic beyond most interviews; it pays off in a handful of well-known hard problems (reconstruct an itinerary from tickets, chain pairs end to end, crack a safe with the shortest code string) where "use every edge exactly once" is the whole question.

Intuition

An Eulerian path uses every edge exactly once; an Eulerian circuit also ends where it started. Unlike Hamiltonian paths (every vertex once, NP-hard), Eulerian paths have a simple test and a linear-time construction.

When does one exist? Ignore isolated vertices; the remaining vertices must be connected (for directed graphs: connected when edge directions are ignored, and the construction below confirms the rest). Then:

Graph	Circuit exists iff	Path exists iff
Undirected	every degree is even	exactly 0 or 2 vertices have odd degree (the path runs between them)
Directed	in-degree = out-degree everywhere	additionally allowed: one vertex with out - in = 1 (start) and one with in - out = 1 (end)

Why: every time a walk passes through a vertex it uses one edge in and one edge out, so only the endpoints can be unbalanced.

Hierholzer's algorithm. Walk from the start, deleting each edge as you use it, until you are stuck. With the degree conditions you can only get stuck at the end vertex; but you may have skipped edges hanging off earlier vertices. Those remaining edges form closed loops, and each loop can be spliced into the walk at a vertex where it touches. The stack formulation does the splicing automatically: keep the current walk on a stack; when the top vertex has an unused edge, follow it; when it has none, pop it onto the answer. The answer comes out in reverse.

When to use it in interviews / OAs

• "Use every ticket / domino / connection exactly once" and output the order: reconstruct itinerary (lexicographically smallest), valid arrangement of pairs.
• Shortest string containing every length-n code (cracking the safe): a de Bruijn sequence, i.e. an Eulerian circuit on the graph of (n - 1)-length strings.
• "Can this drawing be traced without lifting the pen?" Degree parity.
• Chaining words where each word's last letter must equal the next word's first letter, using all words: letters are vertices, words are edges.

Template

Directed graph

from collections import defaultdict


def euler_path_directed(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    adj: list[list[int]] = [[] for _ in range(n)]
    out_deg, in_deg = [0] * n, [0] * n
    for u, v in edges:
        adj[u].append(v)
        out_deg[u] += 1
        in_deg[v] += 1
    start = next((v for v in range(n) if out_deg[v] > 0), 0)
    plus = minus = 0
    for v in range(n):
        d = out_deg[v] - in_deg[v]
        if d == 1:
            plus += 1
            start = v  # a path must start at the vertex with one extra out-edge
        elif d == -1:
            minus += 1
        elif d != 0:
            return None
    if (plus, minus) not in ((0, 0), (1, 1)):
        return None
    ptr = [0] * n  # next unused edge of each vertex
    stack, path = [start], []
    while stack:
        u = stack[-1]
        if ptr[u] < len(adj[u]):
            ptr[u] += 1
            stack.append(adj[u][ptr[u] - 1])
        else:
            path.append(stack.pop())  # stuck: u is final at this position
    path.reverse()
    return path if len(path) == len(edges) + 1 else None  # shorter: edges not connected

Undirected graph

Each edge sits in two adjacency lists, so mark it used by id and skip it from the other side.

def euler_path_undirected(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    odd = [v for v in range(n) if len(adj[v]) % 2]
    if len(odd) not in (0, 2):
        return None
    start = odd[0] if odd else next((v for v in range(n) if adj[v]), 0)
    used = [False] * len(edges)
    ptr = [0] * n
    stack, path = [start], []
    while stack:
        u = stack[-1]
        while ptr[u] < len(adj[u]) and used[adj[u][ptr[u]][1]]:
            ptr[u] += 1  # already used from the other endpoint
        if ptr[u] < len(adj[u]):
            v, i = adj[u][ptr[u]]
            used[i] = True
            stack.append(v)
        else:
            path.append(stack.pop())
    return path[::-1] if len(path) == len(edges) + 1 else None

Reconstruct itinerary (lexicographically smallest)

Sorting each adjacency list makes Hierholzer pick the smallest destination first; the dead-end branch is pushed to the answer first, which is exactly what keeps the final order valid and minimal.

def find_itinerary(tickets: list[tuple[str, str]], start: str = "JFK") -> list[str]:
    graph: dict[str, list[str]] = defaultdict(list)
    for a, b in sorted(tickets, reverse=True):
        graph[a].append(b)  # reverse-sorted, so pop() returns the smallest
    route, stack = [], [start]
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        route.append(stack.pop())
    return route[::-1]

De Bruijn sequence (cracking the safe)

Vertices are the k^(n-1) strings of length n - 1; appending digit d to vertex v is an edge to v[1:] + d. Every vertex has k edges in and out, so an Eulerian circuit exists and spells every length-n code exactly once.

def crack_safe(n: int, k: int) -> str:
    start = "0" * (n - 1)
    used: dict[str, int] = {}  # vertex -> how many of its k out-edges are used
    stack = [(start, "")]  # (vertex, digit on the edge that led here)
    out = []
    while stack:
        v, d = stack[-1]
        i = used.get(v, 0)
        if i < k:
            used[v] = i + 1
            stack.append(((v + str(i))[1:], str(i)))
        else:
            stack.pop()
            out.append(d)
    return start + "".join(reversed(out))

Complexity

Every edge is pushed and popped once: O(n + m) time and memory (plus O(m log m) if adjacency lists are sorted for the lexicographic version). The de Bruijn string has length k^n + n - 1, built in O(k^n) steps.

Common pitfalls

• Forgetting connectivity. Correct degrees are not enough; two separate cycles pass the degree test. Checking that the result uses all m edges catches it.
• Wrong start vertex. For a path (not a circuit), start at the odd-degree vertex (undirected) or the vertex with out - in = 1 (directed).
• Greedy without backtracking. Simply always taking the smallest next airport can strand you before using all tickets. Hierholzer's post-order handles it with no backtracking at all.
• Recursion depth. A recursive Hierholzer recurses once per edge; with 10^5 edges Python overflows. Use the explicit stack.
• Undirected double counting. Without per-edge used flags, an undirected edge is walked twice (once from each end).
• Multi-digit labels in de Bruijn constructions: the slicing trick assumes single-character digits (k <= 10).

Interview variations

• Reconstruct itinerary. The template above; tickets may repeat, so keep duplicates in the lists.
• Valid arrangement of pairs. Directed Euler path where pairs [a, b] are edges between values; use a dictionary for adjacency and degrees.
• Cracking the safe. De Bruijn sequence as above.
• Can all words form a circle? Each word is an edge from its first to its last letter; check in/out degrees plus connectivity.
• Fewest pen strokes to draw every edge. In an undirected graph, sum max(1, odd_vertices / 2) over the connected components that have edges: each stroke is a trail, and a component needs one trail per pair of odd vertices.
• Chinese postman (walk every edge at least once, minimum total) generalizes this with shortest paths between odd vertices; rarely asked.