Eulerian Path and Circuit — Hierholzer's Algorithm

Euler's solution to the Seven Bridges of Königsberg in 1736 is considered the founding paper of graph theory and one of the earliest proofs in discrete mathematics. The question was whether a walker could cross all seven bridges of Königsberg exactly once and return to the start. Euler proved it was impossible — and in doing so invented the mathematical framework we now call graph theory.

The algorithm itself (Hierholzer's, 1873) is elegant: find a cycle, find a node on the cycle with unused edges, extend. The linear time O(E) complexity is achievable because each edge is traversed exactly once. In bioinformatics, Eulerian paths in de Bruijn graphs are how genome assemblers reconstruct DNA sequences from millions of short reads — perhaps the most important modern application of 230-year-old graph theory.

Existence Conditions

Undirected graph: - Eulerian circuit exists ↔ graph is connected AND every vertex has even degree - Eulerian path exists ↔ graph is connected AND exactly 0 or 2 vertices have odd degree (path goes from one odd-degree vertex to the other)

Directed graph: - Eulerian circuit exists ↔ strongly connected AND every vertex: in-degree = out-degree - Eulerian path exists ↔ weakly connected AND at most one vertex has out-degree - in-degree = 1 (start) AND at most one vertex has in-degree - out-degree = 1 (end)

from collections import defaultdict

def has_eulerian_circuit(adj: dict) -> bool:
    # All vertices must have even degree
    return all(len(neighbours) % 2 == 0 for neighbours in adj.values())

def has_eulerian_path(adj: dict) -> bool:
    odd_degree = sum(1 for v in adj if len(adj[v]) % 2 != 0)
    return odd_degree == 0 or odd_degree == 2

# Königsberg bridges — all 4 vertices have odd degree
konigsberg = {'A':['B','B','D'], 'B':['A','A','C','C'], 'C':['B','B','D'], 'D':['A','C']}
print(has_eulerian_circuit(konigsberg))  # False
print(has_eulerian_path(konigsberg))     # False — no Eulerian path!

Hierholzer's Algorithm — O(E)

1. Start at any vertex (or an odd-degree vertex for Eulerian path)
2. Walk randomly, never reusing edges, until stuck
3. If stuck at start: done if all edges used; otherwise, find a vertex on the current circuit with unused edges
4. Insert a new circuit from that vertex into the main circuit
5. Repeat until all edges are used

from collections import defaultdict

def eulerian_circuit(adj_input: dict) -> list:
    """
    Find Eulerian circuit using Hierholzer's algorithm.
    adj_input: {vertex: [neighbours]} — will be modified
    """
    adj = defaultdict(list)
    for u, neighbours in adj_input.items():
        adj[u].extend(neighbours)

    # Check all vertices have even degree
    if not all(len(adj[v]) % 2 == 0 for v in adj):
        return []  # No Eulerian circuit

    start = next(iter(adj))
    stack = [start]
    circuit = []

    while stack:
        v = stack[-1]
        if adj[v]:
            u = adj[v].pop()
            adj[u].remove(v)  # remove reverse edge for undirected
            stack.append(u)
        else:
            circuit.append(stack.pop())

    return circuit[::-1]

adj = {0:[1,2], 1:[0,2], 2:[0,1]}
print(eulerian_circuit(adj))  # [0, 1, 2, 0] (triangle)

The Seven Bridges of Königsberg

Euler proved in 1736 that the city of Königsberg (now Kaliningrad) has no Eulerian path. The city has 4 landmasses connected by 7 bridges. Each landmass has an odd number of bridges (3, 5, 3, 3). For an Eulerian path, at most 2 vertices can have odd degree. With 4 odd-degree vertices, neither an Eulerian path nor circuit exists.

This is the founding problem of graph theory.

Applications

• DNA fragment assembly: Eulerian path in de Bruijn graphs reassembles genome sequences
• Route planning: Postman problem — minimum edges to add to make graph Eulerian
• Circuit design: Drawing PCB traces without lifting the pen
• Puzzle solving: Draw-without-lifting-pen puzzles

Frequently Asked Questions