Euler Path and Circuit: Hierholzer's Algorithm

An Euler path visits every edge in a graph exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex. These concepts were born from the famous Konigsberg bridge problem in 1736, where Euler proved that no walk could cross all seven bridges exactly once.

Understanding Euler paths and circuits is valuable for solving problems involving traversal of all edges: circuit board trace routing, snow plow routing (Chinese postman problem), DNA fragment assembly, and network protocol design.

Euler Path vs Euler Circuit vs Hamiltonian

These three concepts are easy to confuse:

Euler Path: Visit every EDGE exactly once. Start and end at different vertices.

Euler Circuit: Visit every EDGE exactly once AND return to the starting vertex.

Hamiltonian Path: Visit every VERTEX exactly once. Edges may be skipped or reused.

The key difference: Euler focuses on edges, Hamilton focuses on vertices.

Property	Euler Path	Euler Circuit	Hamiltonian Path
Visits	Every edge once	Every edge once	Every vertex once
Returns to start	No	Yes	Optional
Existence check	O(V) - degree check	O(V) - degree check	NP-complete
Finding it	O(E) - Hierholzer’s	O(E) - Hierholzer’s	Exponential

Conditions for Existence

Undirected Graphs

Euler Circuit exists if and only if:

1. The graph is connected (ignoring isolated vertices)
2. Every vertex has even degree

Euler Path exists if and only if:

1. The graph is connected (ignoring isolated vertices)
2. Exactly 0 or 2 vertices have odd degree

If 0 vertices have odd degree, the Euler path is also an Euler circuit. If exactly 2 vertices have odd degree, the path must start at one odd-degree vertex and end at the other.

Directed Graphs

Euler Circuit exists if and only if:

1. The graph is connected (weakly connected, all edges in one component)
2. Every vertex has equal in-degree and out-degree

Euler Path exists if and only if:

1. The graph is connected
2. At most one vertex has out-degree - in-degree = 1 (start vertex)
3. At most one vertex has in-degree - out-degree = 1 (end vertex)
4. All other vertices have equal in-degree and out-degree

Checking Conditions in Python

def check_euler_undirected(graph, num_nodes):
    """
    Check if an undirected graph has an Euler path or circuit.
    graph: adjacency list
    Returns: 'circuit', 'path', or 'none'
    """
    # Check connectivity (ignore isolated nodes)
    non_isolated = [i for i in range(num_nodes) if graph[i]]
    if not non_isolated:
        return 'circuit'  # Empty graph

    visited = set()
    stack = [non_isolated[0]]
    visited.add(non_isolated[0])

    while stack:
        node = stack.pop()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

    if any(i not in visited for i in non_isolated):
        return 'none'  # Not connected

    # Count odd-degree vertices
    odd_count = sum(1 for i in range(num_nodes) if len(graph[i]) % 2 == 1)

    if odd_count == 0:
        return 'circuit'
    elif odd_count == 2:
        return 'path'
    else:
        return 'none'


def check_euler_directed(graph, num_nodes):
    """
    Check if a directed graph has an Euler path or circuit.
    graph: adjacency list (directed)
    Returns: ('circuit', None, None), ('path', start, end), or ('none', None, None)
    """
    in_degree = [0] * num_nodes
    out_degree = [0] * num_nodes

    for u in range(num_nodes):
        out_degree[u] = len(graph[u])
        for v in graph[u]:
            in_degree[v] += 1

    start_nodes = []
    end_nodes = []

    for i in range(num_nodes):
        diff = out_degree[i] - in_degree[i]
        if diff == 1:
            start_nodes.append(i)
        elif diff == -1:
            end_nodes.append(i)
        elif diff != 0:
            return ('none', None, None)

    if len(start_nodes) == 0 and len(end_nodes) == 0:
        return ('circuit', None, None)
    elif len(start_nodes) == 1 and len(end_nodes) == 1:
        return ('path', start_nodes[0], end_nodes[0])
    else:
        return ('none', None, None)

Hierholzer’s Algorithm

Hierholzer’s algorithm finds an Euler circuit (or path) in O(E) time. The idea is elegant: start at any vertex, follow edges until you return to the start (forming a cycle). Then, for any vertex in the cycle that has unused edges, start a new sub-circuit and splice it into the main circuit.

Euler Circuit in Undirected Graph

from collections import defaultdict

def find_euler_circuit_undirected(edges, num_nodes):
    """
    Find an Euler circuit in an undirected graph.
    edges: list of (u, v) tuples
    Returns: list of vertices forming the circuit
    """
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # Check if Euler circuit exists
    for node in graph:
        if len(graph[node]) % 2 != 0:
            return []  # No Euler circuit

    # Hierholzer's algorithm
    stack = [0]  # Start from node 0 (any node works)
    circuit = []

    while stack:
        node = stack[-1]
        if graph[node]:
            neighbor = graph[node].pop()
            # Remove the reverse edge too
            graph[neighbor].remove(node)
            stack.append(neighbor)
        else:
            circuit.append(stack.pop())

    circuit.reverse()
    return circuit

The remove operation on lists is O(degree) which makes this O(V*E) in the worst case. For better performance, use edge indices:

def find_euler_circuit_fast(edges, num_nodes):
    """
    Efficient Euler circuit using edge indices.
    O(E) time complexity.
    """
    graph = defaultdict(list)
    edge_used = [False] * len(edges)

    for idx, (u, v) in enumerate(edges):
        graph[u].append((v, idx))
        graph[v].append((u, idx))

    # Use pointer array to avoid rescanning used edges
    ptr = defaultdict(int)  # Current edge pointer for each node

    stack = [0]
    circuit = []

    while stack:
        node = stack[-1]
        # Find next unused edge
        while ptr[node] < len(graph[node]):
            neighbor, edge_idx = graph[node][ptr[node]]
            ptr[node] += 1
            if not edge_used[edge_idx]:
                edge_used[edge_idx] = True
                stack.append(neighbor)
                break
        else:
            # No more unused edges from this node
            circuit.append(stack.pop())

    circuit.reverse()
    return circuit

Euler Path in Undirected Graph

To find an Euler path (not circuit), start from one of the two odd-degree vertices.

def find_euler_path_undirected(edges, num_nodes):
    """
    Find an Euler path in an undirected graph.
    Returns: list of vertices forming the path
    """
    graph = defaultdict(list)
    edge_used = [False] * len(edges)

    for idx, (u, v) in enumerate(edges):
        graph[u].append((v, idx))
        graph[v].append((u, idx))

    # Find odd-degree vertices
    odd_vertices = [v for v in graph if len(graph[v]) % 2 == 1]

    if len(odd_vertices) not in (0, 2):
        return []  # No Euler path

    # Start from an odd-degree vertex (or any vertex for circuit)
    start = odd_vertices[0] if odd_vertices else 0

    ptr = defaultdict(int)
    stack = [start]
    path = []

    while stack:
        node = stack[-1]
        while ptr[node] < len(graph[node]):
            neighbor, edge_idx = graph[node][ptr[node]]
            ptr[node] += 1
            if not edge_used[edge_idx]:
                edge_used[edge_idx] = True
                stack.append(neighbor)
                break
        else:
            path.append(stack.pop())

    path.reverse()
    return path

Euler Circuit/Path in Directed Graph

For directed graphs, the algorithm is simpler because there are no reverse edges to handle.

def find_euler_path_directed(graph, num_nodes):
    """
    Find an Euler path/circuit in a directed graph.
    graph: adjacency list (list of lists)
    Returns: list of vertices
    """
    in_degree = [0] * num_nodes
    out_degree = [0] * num_nodes

    for u in range(num_nodes):
        out_degree[u] = len(graph[u])
        for v in graph[u]:
            in_degree[v] += 1

    # Find start node
    start = 0
    for i in range(num_nodes):
        if out_degree[i] - in_degree[i] == 1:
            start = i
            break

    # Use adjacency list as stack (pop from end)
    adj = [list(graph[i]) for i in range(num_nodes)]
    stack = [start]
    path = []

    while stack:
        node = stack[-1]
        if adj[node]:
            stack.append(adj[node].pop())
        else:
            path.append(stack.pop())

    path.reverse()
    return path

Example

# Directed graph with Euler path
# 0 -> 1 -> 2 -> 0 -> 3 -> 4 -> 0
graph = [
    [1, 3],   # 0
    [2],      # 1
    [0],      # 2
    [4],      # 3
    [0]       # 4
]

path = find_euler_path_directed(graph, 5)
print(path)  # [0, 3, 4, 0, 1, 2, 0] (or similar valid Euler circuit)

Application: Reconstruct Itinerary (LeetCode 332)

Given a list of airline tickets, reconstruct the itinerary in lexical order starting from “JFK”.

def find_itinerary(tickets):
    """
    LeetCode 332: Reconstruct Itinerary.
    Find Euler path starting from JFK in lexical order.
    """
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)

    route = []

    def dfs(airport):
        while graph[airport]:
            next_airport = graph[airport].pop()
            dfs(next_airport)
        route.append(airport)

    dfs('JFK')
    return route[::-1]


# Example
tickets = [
    ['JFK', 'SFO'],
    ['JFK', 'ATL'],
    ['SFO', 'ATL'],
    ['ATL', 'JFK'],
    ['ATL', 'SFO']
]
print(find_itinerary(tickets))
# ['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']

The trick is sorting destinations in reverse so that popping from the list gives the lexicographically smallest next airport.

Application: Valid Arrangement of Pairs (LeetCode 2097)

Given pairs where end[i] must match start[i+1], find a valid arrangement. This is finding an Euler path in a directed graph.

def valid_arrangement(pairs):
    """
    LeetCode 2097: Valid Arrangement of Pairs.
    """
    graph = defaultdict(list)
    in_deg = defaultdict(int)
    out_deg = defaultdict(int)

    for start, end in pairs:
        graph[start].append(end)
        out_deg[start] += 1
        in_deg[end] += 1

    # Find start node (out_degree - in_degree == 1)
    start_node = pairs[0][0]
    for node in graph:
        if out_deg[node] - in_deg[node] == 1:
            start_node = node
            break

    # Hierholzer's
    stack = [start_node]
    path = []

    while stack:
        node = stack[-1]
        if graph[node]:
            stack.append(graph[node].pop())
        else:
            path.append(stack.pop())

    path.reverse()

    # Convert path to pairs
    result = []
    for i in range(len(path) - 1):
        result.append([path[i], path[i + 1]])

    return result

The Chinese Postman Problem

The Chinese Postman Problem asks: what is the shortest closed walk that visits every edge at least once? If an Euler circuit exists, the answer is the sum of all edge weights. If not, you need to duplicate some edges to make all vertices have even degree.

def chinese_postman(graph, num_nodes, edges):
    """
    Find minimum cost walk that traverses every edge at least once.
    For simple cases: find odd-degree vertices and add shortest
    paths between pairs.
    """
    total_weight = sum(w for _, _, w in edges)

    # Find odd-degree vertices
    degree = [0] * num_nodes
    for u, v, w in edges:
        degree[u] += 1
        degree[v] += 1

    odd_vertices = [v for v in range(num_nodes) if degree[v] % 2 == 1]

    if not odd_vertices:
        return total_weight  # Euler circuit exists

    # For the general case, find minimum weight perfect matching
    # of odd-degree vertices using shortest paths between them.
    # This is simplified for illustration.

    from math import inf
    import heapq

    def dijkstra_from(source):
        dist = [inf] * num_nodes
        dist[source] = 0
        pq = [(0, source)]
        adj = [[] for _ in range(num_nodes)]
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))

        while pq:
            d, node = heapq.heappop(pq)
            if d > dist[node]:
                continue
            for neighbor, weight in adj[node]:
                nd = d + weight
                if nd < dist[neighbor]:
                    dist[neighbor] = nd
                    heapq.heappush(pq, (nd, neighbor))
        return dist

    # Compute shortest paths between all odd-degree pairs
    odd_count = len(odd_vertices)
    pair_dist = [[inf] * odd_count for _ in range(odd_count)]

    for i, v in enumerate(odd_vertices):
        dist = dijkstra_from(v)
        for j, u in enumerate(odd_vertices):
            pair_dist[i][j] = dist[u]

    # Find minimum weight perfect matching (brute force for small cases)
    def min_matching(mask, n, costs):
        if mask == (1 << n) - 1:
            return 0

        # Find first unmatched
        first = -1
        for i in range(n):
            if not (mask & (1 << i)):
                first = i
                break

        result = inf
        for j in range(first + 1, n):
            if not (mask & (1 << j)):
                cost = costs[first][j] + min_matching(
                    mask | (1 << first) | (1 << j), n, costs
                )
                result = min(result, cost)

        return result

    extra_cost = min_matching(0, odd_count, pair_dist)
    return total_weight + extra_cost

De Bruijn Sequences

A De Bruijn sequence contains every possible subsequence of length n over an alphabet exactly once. It can be constructed by finding an Euler circuit in the De Bruijn graph.

def de_bruijn_sequence(k, n):
    """
    Generate a De Bruijn sequence for alphabet size k and length n.
    Uses Euler circuit on the De Bruijn graph.
    """
    from collections import defaultdict

    # Build De Bruijn graph
    # Nodes: all strings of length n-1
    # Edges: all strings of length n (connecting prefix to suffix)
    graph = defaultdict(list)

    for i in range(k ** n):
        # Convert number to base-k string of length n
        s = []
        num = i
        for _ in range(n):
            s.append(num % k)
            num //= k
        s.reverse()

        prefix = tuple(s[:-1])
        suffix = tuple(s[1:])
        graph[prefix].append(suffix)

    # Find Euler circuit
    start = tuple([0] * (n - 1))
    stack = [start]
    path = []

    adj = {k: list(v) for k, v in graph.items()}

    while stack:
        node = stack[-1]
        if adj.get(node):
            stack.append(adj[node].pop())
        else:
            path.append(stack.pop())

    path.reverse()

    # Build sequence from path
    sequence = list(path[0])
    for i in range(1, len(path)):
        sequence.append(path[i][-1])

    return sequence[:k**n]


# Example: Binary De Bruijn sequence of length 3
seq = de_bruijn_sequence(2, 3)
print(seq)  # Contains all 3-bit subsequences

Complexity Summary

Operation	Time	Space
Check Euler existence	O(V + E)	O(V)
Find Euler circuit/path	O(E)	O(E)
Chinese Postman (brute force matching)	O(2^k * k^2 + VElogV)	O(V + E)

Where k is the number of odd-degree vertices (always even, usually small).

Practice Problems

1. Reconstruct Itinerary (LeetCode 332) - Euler path with lexical order
2. Valid Arrangement of Pairs (LeetCode 2097) - Euler path on pairs
3. Cracking the Safe (LeetCode 753) - De Bruijn sequence via Euler circuit
4. USACO “Riding the Fences” - Classic Euler path
5. Chinese Postman Problem - Edge traversal optimization

Key Takeaways

Euler paths visit every edge exactly once. The existence check is simple: count odd-degree vertices (must be 0 or 2 for undirected graphs). Hierholzer’s algorithm finds the path in O(E) time by building cycles and splicing them. Directed graphs use in-degree/out-degree conditions instead. The Chinese Postman problem and De Bruijn sequences are practical applications. Do not confuse Euler (edges) with Hamiltonian (vertices). Finding Hamiltonian paths is NP-complete, while Euler paths are efficiently solvable.