Graph Algorithms7 min read

Eulerian Path & Circuit

Can you cross every bridge exactly once? Euler answered this in 1736
existence check:Fast · \(O(V+E)\)Hierholzer's:Linear · \(O(V+E)\)total:\(O(V+E)\)

In 1736, the city of Königsberg had seven bridges connecting its islands. A local puzzle asked: can you walk through the city crossing every bridge exactly once and return home?

Leonhard Euler proved it was impossible — and in doing so, invented graph theory. The key insight he found still works today: you can solve the puzzle by looking only at how many bridges touch each landmass.

The Two Questions

An Eulerian circuit starts and ends at the same spot, using every edge exactly once (like coming home after crossing all bridges). An Eulerian path uses every edge exactly once but can end somewhere different from where it started.

The Magic Degree Condition (Undirected Graphs)

Every time you enter a vertex through one bridge, you need another bridge to leave — unless it's the very start or end. This means:

  • Eulerian circuit exists ↔ graph is connected and every vertex has even degree.
  • Eulerian path exists ↔ graph is connected and exactly two vertices have odd degree (those are the start and end).

Königsberg had four landmasses, all with odd degree — so neither a circuit nor a path was possible. Euler saw this in seconds.

Directed Graphs

For directed graphs, replace "even degree" with balanced in/out-degree: an Eulerian circuit needs every vertex to have in-degree = out-degree. An Eulerian path needs exactly one vertex with out-degree = in-degree + 1 (start) and one with in-degree = out-degree + 1 (end).

Hierholzer's Algorithm: Building the Route

Checking existence is trivial — actually building the route takes a bit more cleverness. Hierholzer's method works like this:

  1. Start anywhere and greedily follow edges (marking them used) until you're stuck — this gives you a circuit, but it might skip some edges.
  2. Find any vertex on your circuit that still has unused edges. Start a new mini-circuit from there.
  3. Splice the mini-circuit into the main circuit at that vertex's position.
  4. Repeat until no unused edges remain.

With the right data structure (a doubly-linked list), each splice is \(O(1)\), giving \(O(V+E)\) overall.

Note: The Königsberg bridges had four odd-degree landmasses. Euler's rule says you need 0 or 2 odd-degree vertices for the walk to exist. Four is two too many — the puzzle has no solution!

Eulerian Path — Hierholzer's Algorithm

from collections import defaultdict


def eulerian_path(n, edges):
    adj = defaultdict(list)
    degree = [0] * n
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
        degree[u] += 1
        degree[v] += 1


    # Find start: odd-degree vertex (or any vertex for circuit)
    odd = [i for i in range(n) if degree[i] % 2 == 1]
    start = odd[0] if odd else 0


    path = []
    stack = [start]
    while stack:
        v = stack[-1]
        if adj[v]:
            u = adj[v].pop()
            adj[u].remove(v)  # undirected: remove both directions
            stack.append(u)
        else:
            path.append(stack.pop())
    return path


# Simple path: 0-1-2-3-1 (vertices 0 and 3 have odd degree)
edges = [(0,1),(1,2),(2,3),(3,1),(1,0)]
print(eulerian_path(4, edges))
Output
[0, 1, 3, 2, 1, 0]

Complexity

🔢 Existence checkCount in/out degrees and run BFS/DFS to check connectivity
Count degrees — very fast\(O(V+E)\)
🗺️ Hierholzer's constructionEvery edge is traversed once; splice operations are \(O(1)\) with a linked list
Linear — each edge visited once\(O(V+E)\)
➕ Virtual edge trickAdd a fake edge end→start to turn an Eulerian path into a circuit; remove it from the result
Constant extra cost\(O(1)\)

Quick check

The Königsberg bridge problem has 4 landmasses, all with an odd number of bridges. Why is the walk impossible?

Continue reading

Hamiltonian Path
Visit every house exactly once — far harder than every bridge
→
BFS & DFS Revisited
Two ways to explore a graph — level by level, or all the way in
→
Tarjan's Algorithm
Find all tightly-knit groups in a directed graph in one pass
→