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

Directed Eulerian Paths and Circuits

The algorithm for directed graphs is similar to undirected, but when traversing, you only pop an outgoing edge from the current vertex's adjacency list — you don't remove reverse edges because they don't exist as separate entries. The code is slightly simpler: no adj[u].remove(v) step.

from collections import defaultdict

def eulerian_circuit_directed(adj_input: dict) -> list:
    """
    Find Eulerian circuit in directed graph.
    adj_input: {vertex: [outgoing neighbours]}
    """
    adj = defaultdict(list)
    for u, neighbours in adj_input.items():
        adj[u].extend(neighbours)
    
    # Check in-degree == out-degree (requires degree computation outside this snippet)
    # For simplicity, assume condition met
    start = next(iter(adj))
    stack = [start]
    circuit = []
    while stack:
        v = stack[-1]
        if adj[v]:
            u = adj[v].pop()
            stack.append(u)
        else:
            circuit.append(stack.pop())
    return circuit[::-1]

digraph = {0:[1,2], 1:[2], 2:[0]}
print(eulerian_circuit_directed(digraph))  # [0,1,2,0]

Performance and Implementation Trade-offs

Hierholzer's algorithm is O(E) time and O(V+E) space (to store adjacency lists). The iterative stack version uses O(E) additional space in the worst case for the stack. The recursive version uses O(E) call stack memory, which can be prohibitive for large graphs.

Important: The algorithm modifies the adjacency list — each edge is removed when traversed. This means you must copy the input if you need the original graph later. For read-heavy applications, consider a read-only approach: mark edges as used instead of deleting them. That increases memory but preserves the graph.

C++ Implementation of Hierholzer's Algorithm

While the Python version is great for prototyping, C++ is often used in performance-critical bioinformatics pipelines. The implementation below demonstrates Hierholzer's algorithm for both undirected and directed graphs. Key differences from Python: you must manage edge removal carefully — for undirected graphs, we use std::multiset to allow multiple edges and erase a single element using an iterator. For directed graphs, we only pop from the outgoing list.

Undirected Version: Uses std::unordered_map<int, std::multiset<int>> to store adjacency. When traversing edge u→v, we remove v from adj[u] and u from adj[v] (erase one iterator each).

Directed Version: Uses std::unordered_map<int, std::vector<int>> and pops from the back (which is O(1) amortized). No reverse edge removal needed.

The iterative stack avoids recursion depth issues. The circuit is built in reverse and returned in correct order.

#include <bits/stdc++.h>
using namespace std;

// Undirected Hierholzer
vector<int> eulerian_circuit_undirected(unordered_map<int, multiset<int>>& adj) {
    for (auto& [v, neighbours] : adj) {
        if (neighbours.size() % 2 != 0) return {}; // not Eulerian
    }
    int start = adj.begin()->first;
    stack<int> st;
    st.push(start);
    vector<int> circuit;
    while (!st.empty()) {
        int v = st.top();
        auto& neighbors = adj[v];
        if (!neighbors.empty()) {
            auto it = neighbors.begin();
            int u = *it;
            neighbors.erase(it);           // remove from v
            adj[u].erase(adj[u].find(v));  // remove reverse from u
            st.push(u);
        } else {
            circuit.push_back(v);
            st.pop();
        }
    }
    reverse(circuit.begin(), circuit.end());
    return circuit;
}

// Directed Hierholzer
vector<int> eulerian_circuit_directed(unordered_map<int, vector<int>>& adj) {
    // Assume in-degree == out-degree verified separately
    int start = adj.begin()->first;
    stack<int> st;
    st.push(start);
    vector<int> circuit;
    while (!st.empty()) {
        int v = st.top();
        auto& neighbors = adj[v];
        if (!neighbors.empty()) {
            int u = neighbors.back();
            neighbors.pop_back();
            st.push(u);
        } else {
            circuit.push_back(v);
            st.pop();
        }
    }
    reverse(circuit.begin(), circuit.end());
    return circuit;
}

Fleury's Algorithm: A Safe-Bridge Alternative

Before Hierholzer, Fleury (1883) proposed a simpler greedy algorithm: start from an odd-degree vertex (if one exists), and at each step, choose an edge that is not a bridge unless no other choice exists. A bridge is an edge whose removal disconnects the graph. By avoiding bridges, you ensure you don't cut off unused edges from the remaining subgraph.

Algorithm: 1. Start at a vertex (odd-degree if path, any if circuit). 2. For each adjacent edge, test if it's a bridge using DFS. If it's a bridge and there are other non-bridge edges, skip it. 3. Traverse the chosen edge, remove it, and move to the next vertex. 4. Repeat until all edges are used.

Complexity: O(E²) because for each edge you test bridges with a DFS (O(E)). This makes it impractical for large graphs. Hierholzer's O(E) is strictly better.

Why learn Fleury? It provides a different perspective — the concept of safe edges (non-bridges) is useful in network reliability. Also, some interview questions test understanding of bridge detection in this context.

Contrast Table:

Starting Vertex Selection for Eulerian Paths

For an Eulerian circuit, you can start at any vertex that has edges (degree > 0). The algorithm will return a circuit covering all edges. However, for an Eulerian path (not circuit), the starting vertex must be one of the two odd-degree vertices (if exactly two exist). If all vertices have even degree, the graph has a circuit, so any vertex works for both circuit and path.

Why? In an Eulerian path, the start vertex must have one more outgoing than incoming (or degree odd in undirected) because the path ends elsewhere. The vertex with odd degree (or out-in = 1) is the only one that can serve as start if you want to use all edges.

How to choose in code: 1. Compute degrees (in/out for directed, just degree for undirected). 2. If exactly two vertices have odd degree (undirected) or exactly one source (out-in=1) and one sink (in-out=1), pick the odd-degree/source vertex as start. 3. If all even (or in=out), pick any vertex — the graph is Eulerian. 4. If no such vertex exists, no Eulerian path exists; return [] before running algorithm.

Edge case: For directed graphs with an Eulerian circuit, you can start at any vertex. But if an Eulerian path exists, you must start at the source vertex. The algorithm still works: if you start at the wrong vertex, you might get a circuit that doesn't cover all edges, or you'll get stuck early.

def find_start_vertex_undirected(adj: dict) -> int:
    odd_vertices = [v for v, neigh in adj.items() if len(neigh) % 2 != 0]
    if len(odd_vertices) == 0:
        return next(iter(adj))  # circuit, any vertex
    elif len(odd_vertices) == 2:
        return odd_vertices[0]  # start at one of the two odd-degree vertices
    else:
        return None  # no Eulerian path

def find_start_vertex_directed(in_deg: dict, out_deg: dict) -> int:
    start = [v for v in out_deg if out_deg[v] - in_deg.get(v,0) == 1]
    end = [v for v in in_deg if in_deg[v] - out_deg.get(v,0) == 1]
    if len(start) == 1 and len(end) == 1:
        return start[0]
    elif len(start) == 0 and len(end) == 0:
        return next(iter(out_deg))  # circuit
    else:
        return None

Advantages and Disadvantages of Hierholzer's Algorithm

Hierholzer's algorithm is the standard for finding Eulerian paths and circuits. Here are its key strengths and weaknesses:

When to avoid Hierholzer: - If your graph is dynamic (edges added/removed frequently), the static algorithm must be re-run. - If you need to find all Eulerian circuits (enumeration is #P-complete), you need different approaches. - For graphs that are Hamiltonian-like (vertex coverage), Hierholzer is irrelevant.

When it shines: - In any application where you need one Eulerian traversal: street sweeping, DNA assembly, network troubleshooting.

The Chinese Postman Problem (Route Inspection)

The Chinese Postman Problem (also called Route Inspection Problem) asks: find the shortest closed walk that visits every edge at least once and returns to the start. If the graph is Eulerian (all even degrees), the answer is simply the sum of edge weights along an Eulerian circuit. If not, you must duplicate some edges (add traversals) to make all vertices even degree, then find an Eulerian circuit on the augmented graph.

How it works: 1. Identify vertices with odd degree (they come in pairs). 2. Compute shortest paths between all pairs of odd-degree vertices (using Floyd-Warshall or Dijkstra from each). 3. Solve a minimum-weight perfect matching on the odd-degree vertices: pair them up so that the sum of shortest path distances is minimized. This pairing tells you which edges to traverse twice (or add as virtual edges). 4. Add those shortest paths to the graph (duplicating edges), then find an Eulerian circuit on the resulting Eulerian graph.

Real-world applications: - Mail delivery: Postman needs to walk every street at least once; minimize total distance. - Snow plowing: Plow every road; duplicates add extra passes. - Street sweeping: Same idea. - Network inspection: Inspect every cable/fiber segment; extra traversals add time.

Complexity: O(V³) with Floyd-Warshall, plus O(k³) for matching where k = number of odd-degree vertices (usually small). For general graphs, this is polynomial and practical for city-scale road networks.

import itertools
from collections import defaultdict

def chinese_postman_cost(adj: dict) -> int:
    # Step 1: find odd-degree vertices
    odd = [v for v, neigh in adj.items() if len(neigh) % 2 != 0]
    if len(odd) == 0:
        return sum(weight for _, _, weight in edges(adj))  # already Eulerian
    
    # Step 2: compute all-pairs shortest paths (Floyd-Warshall)
    vertices = list(adj.keys())
    dist = {v: {u: float('inf') for u in vertices} for v in vertices}
    for v in vertices:
        dist[v][v] = 0
        for u, w in adj[v]:  # assume adj[v] is list of (neighbor, weight)
            dist[v][u] = w
    for k in vertices:
        for i in vertices:
            for j in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # Step 3: minimum weight perfect matching on odd vertices (brute force for small k)
    k = len(odd)
    min_extra = float('inf')
    for perm in itertools.permutations(odd):
        if perm[0] > perm[1]:  # avoid symmetric
            continue
        pairs = list(zip(perm[::2], perm[1::2]))
        total = sum(dist[u][v] for u,v in pairs)
        min_extra = min(min_extra, total)
    return sum(w for _, _, w in edges(adj)) + min_extra

Practice Problems

Sharpen your Eulerian path/circuit skills with these curated problems. They range from direct algorithm implementation to complex variants requiring existence checks and optimizations.

1. LeetCode 332 — Reconstruct Itinerary (Medium)
2. - Given a list of airline tickets (from, to), find an itinerary that uses all tickets exactly once (Eulerian path in a directed graph).
3. - [https://leetcode.com/problems/reconstruct-itinerary/](https://leetcode.com/problems/reconstruct-itinerary/)
4. - Hint: Use Hierholzer with lexical ordering; the graph is guaranteed to have an Eulerian path.
5. CSES — Eulerian Path (Easy)
6. - Directed graph; check existence and output one Eulerian path if it exists.
7. - [https://cses.fi/problemset/task/1699](https://cses.fi/problemset/task/1699)
8. - Straightforward implementation of Hierholzer.
9. CSES — Eulerian Circuit (Easy)
10. - Same as above but circuit.
11. - [https://cses.fi/problemset/task/1698](https://cses.fi/problemset/task/1698)
12. Codeforces — C. Eulerian Path (Medium)
13. - Classic: check if Eulerian path exists, print it.
14. - [https://codeforces.com/problemset/problem/1188/A2](https://codeforces.com/problemset/problem/1188/A2) (actually this is about tree degrees; look for problem 1188B? Not exact. Use: CF 1188A1? Let's correct: CF 500E? We'll point to a known one: CF 25C? I'll provide a more reliable: Open Kattis — Eulerian Path)
15. - Let's use: Open Kattis — Eulerianpath [https://open.kattis.com/problems/eulerianpath](https://open.kattis.com/problems/eulerianpath) (undirected, check existence and output).
16. Codeforces — 723E: One-Way Reform (Hard)
17. - Given an undirected graph, orient edges so that the number of vertices with equal in/out degree is maximized.
18. - [https://codeforces.com/problemset/problem/723/E](https://codeforces.com/problemset/problem/723/E)
19. - Requires understanding of Eulerian graph conditions and matching.
20. SPOJ — WORDS1: Play on Words (Easy)
21. - Given words, determine if you can chain them so last letter of one matches first letter of the next (Eulerian path in a graph of first/last letters).
22. - [https://www.spoj.com/problems/WORDS1/](https://www.spoj.com/problems/WORDS1/)
23. UVA — 10054: The Necklace (Medium)
24. - Given beads with colors on each side, find a necklace arrangement that uses all beads (Eulerian circuit in multigraph).
25. - [https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=995](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=995)

Tip: Start with LeetCode 332 and CSES problems to get comfortable with Hierholzer's algorithm in both directed and undirected settings. Then move to harder problems like Codeforces 723E for deeper insights into degree constraints.