Eulerian Path and Circuit: Traversing All Edges
In 1736, Leonhard Euler tackled a seemingly simple puzzle: could someone walk through the city of Königsberg, crossing each of its seven bridges exactly once? His proof that no such path existed...
Key Insights
- Eulerian paths and circuits solve the problem of traversing every edge exactly once—a fundamentally different challenge from vertex traversal that requires tracking edges rather than nodes.
- The existence of an Eulerian path depends entirely on vertex degrees: circuits need all even degrees, paths need exactly zero or two odd-degree vertices.
- Hierholzer’s algorithm achieves O(E) time complexity by building and splicing circuits, making it the go-to choice for production implementations over the simpler but slower Fleury’s algorithm.
The Bridges of Königsberg
In 1736, Leonhard Euler tackled a seemingly simple puzzle: could someone walk through the city of Königsberg, crossing each of its seven bridges exactly once? His proof that no such path existed didn’t just solve a recreational problem—it invented graph theory.
The Königsberg bridges problem is the original edge traversal challenge. Unlike BFS or DFS where we visit vertices, Eulerian problems ask whether we can traverse every edge exactly once. This distinction matters enormously in practice.
Modern applications are everywhere. Snow plows need routes covering every street once. PCB manufacturing requires drill paths visiting every connection. DNA sequencers reconstruct genomes by walking through overlap graphs. Network analyzers inspect every link. These problems share the same mathematical structure Euler identified nearly three centuries ago.
An Eulerian circuit (or Eulerian cycle) traverses every edge exactly once and returns to the starting vertex. An Eulerian path traverses every edge exactly once but may end at a different vertex. The circuit is the stricter requirement.
Mathematical Foundation: When Do Eulerian Paths Exist?
The beauty of Eulerian problems lies in their simple existence conditions. You can determine whether a solution exists in O(V + E) time—faster than actually finding the path.
For undirected graphs, the rules are straightforward:
- Eulerian circuit exists if and only if every vertex has even degree and the graph is connected (considering only vertices with edges).
- Eulerian path exists if and only if exactly zero or two vertices have odd degree, and the graph is connected.
The intuition is elegant. When you enter a vertex, you must leave it. Each visit consumes two edges (one in, one out). If a vertex has odd degree, you’ll eventually get stuck there—you enter but can’t leave. A circuit tolerates zero such vertices. A path tolerates exactly two: the start and end points.
Here’s how to check these conditions:
from collections import defaultdict
def classify_eulerian(graph: dict[int, list[int]]) -> str:
"""
Determine if an undirected graph has an Eulerian circuit, path, or neither.
Graph is represented as adjacency list: {vertex: [neighbors]}
"""
if not graph:
return "trivial (empty graph)"
# Count odd-degree vertices
odd_degree_count = 0
for vertex, neighbors in graph.items():
if len(neighbors) % 2 == 1:
odd_degree_count += 1
# Check connectivity (only among vertices with edges)
if not is_connected(graph):
return "none (disconnected)"
if odd_degree_count == 0:
return "circuit"
elif odd_degree_count == 2:
return "path"
else:
return "none (too many odd-degree vertices)"
def is_connected(graph: dict[int, list[int]]) -> bool:
"""Check if all vertices with edges are in one connected component."""
vertices_with_edges = [v for v, neighbors in graph.items() if neighbors]
if not vertices_with_edges:
return True
visited = set()
stack = [vertices_with_edges[0]]
while stack:
vertex = stack.pop()
if vertex in visited:
continue
visited.add(vertex)
stack.extend(graph[vertex])
return len(visited) == len(vertices_with_edges)
Graph Representation for Edge Traversal
Standard adjacency lists work for vertex traversal, but edge traversal introduces a complication: we need to track which edges we’ve used, not which vertices we’ve visited. This matters especially for multigraphs (multiple edges between the same vertices).
The naive approach—removing edges from adjacency lists—works but requires careful handling. A cleaner solution uses edge indices:
class EulerianGraph:
"""Graph representation optimized for edge traversal."""
def __init__(self):
self.adj = defaultdict(list) # vertex -> [(neighbor, edge_id), ...]
self.edge_count = 0
self.used_edges = set()
def add_edge(self, u: int, v: int) -> int:
"""Add undirected edge, return edge ID."""
edge_id = self.edge_count
self.edge_count += 1
self.adj[u].append((v, edge_id))
self.adj[v].append((u, edge_id))
return edge_id
def get_unused_neighbor(self, vertex: int) -> tuple[int, int] | None:
"""Return (neighbor, edge_id) for an unused edge, or None."""
for neighbor, edge_id in self.adj[vertex]:
if edge_id not in self.used_edges:
return (neighbor, edge_id)
return None
def mark_used(self, edge_id: int) -> None:
self.used_edges.add(edge_id)
def degree(self, vertex: int) -> int:
"""Return number of unused edges incident to vertex."""
return sum(1 for _, eid in self.adj[vertex] if eid not in self.used_edges)
def vertices(self) -> list[int]:
return list(self.adj.keys())
This representation lets us mark edges as used in O(1) time and check edge availability without modifying the underlying structure.
Hierholzer’s Algorithm: The Efficient Approach
Hierholzer’s algorithm finds Eulerian circuits in O(E) time. The key insight: don’t try to find the perfect path from the start. Instead, build any circuit, then splice in additional circuits at vertices with remaining edges.
The algorithm works as follows:
- Start at any vertex (for circuits) or an odd-degree vertex (for paths).
- Follow unused edges until you return to the start, forming a circuit.
- If unused edges remain, find a vertex on your circuit with unused edges.
- Build another circuit from that vertex.
- Splice the new circuit into your path.
- Repeat until all edges are used.
The stack-based implementation handles splicing implicitly:
def hierholzer(graph: EulerianGraph, start: int = None) -> list[int]:
"""
Find Eulerian path/circuit using Hierholzer's algorithm.
Returns list of vertices in traversal order.
"""
if start is None:
# Find starting vertex: odd-degree vertex for path, any vertex for circuit
start = graph.vertices()[0]
for v in graph.vertices():
if graph.degree(v) % 2 == 1:
start = v
break
stack = [start]
path = []
while stack:
current = stack[-1]
edge = graph.get_unused_neighbor(current)
if edge is None:
# No unused edges: add to path and backtrack
path.append(stack.pop())
else:
# Follow unused edge
neighbor, edge_id = edge
graph.mark_used(edge_id)
stack.append(neighbor)
# Path is built in reverse
return path[::-1]
# Example usage
def demo_hierholzer():
g = EulerianGraph()
# Create a simple graph: 0-1-2-3-0-2
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 0)
g.add_edge(0, 2)
path = hierholzer(g)
print("Eulerian path:", " -> ".join(map(str, path)))
# Output: Eulerian path: 0 -> 1 -> 2 -> 3 -> 0 -> 2
The magic happens in the backtracking. When we hit a dead end (no unused edges), we add the vertex to our result and pop back. This naturally splices circuits together because we only finalize vertices when all their edges are consumed.
Fleury’s Algorithm: The Intuitive Alternative
Fleury’s algorithm takes a simpler approach: always prefer non-bridge edges. A bridge is an edge whose removal disconnects the graph. The rule is “don’t burn bridges unless you must.”
def is_bridge(graph: EulerianGraph, u: int, v: int, edge_id: int) -> bool:
"""
Check if edge (u, v) is a bridge in the remaining graph.
Uses DFS to check connectivity after hypothetical removal.
"""
# Temporarily mark edge as used
graph.mark_used(edge_id)
# Count reachable vertices from u
visited = set()
stack = [u]
while stack:
current = stack.pop()
if current in visited:
continue
visited.add(current)
for neighbor, eid in graph.adj[current]:
if eid not in graph.used_edges:
stack.append(neighbor)
# Restore edge
graph.used_edges.remove(edge_id)
# If v is not reachable from u without this edge, it's a bridge
# (only matters if v has other unused edges)
remaining_edges_at_v = graph.degree(v) - 1 # excluding current edge
return remaining_edges_at_v > 0 and v not in visited
Fleury’s algorithm runs in O(E²) because bridge detection is O(E) and we perform it for each edge. This makes it impractical for large graphs, but it’s easier to understand and implement correctly. Use Hierholzer’s algorithm in production.
Practical Applications
Route optimization: The classic snow plow problem. Given a city’s street network, find a route covering every street with minimal backtracking. If the graph is Eulerian, the solution is optimal. If not, we solve the Chinese Postman Problem (discussed below).
PCB manufacturing: Circuit board drilling requires visiting every connection point. The drill path is an Eulerian path through the connection graph. Minimizing travel time directly reduces manufacturing costs.
Genome assembly: De Bruijn graphs represent DNA sequence overlaps. Each k-mer (substring of length k) is an edge; vertices are (k-1)-mers. Finding an Eulerian path reconstructs the original sequence. This is how modern genome sequencers work.
Network analysis: Packet sniffers that must inspect every link use Eulerian traversals. Network testing that verifies every connection follows the same pattern.
Extensions and Edge Cases
Directed graphs have different conditions. An Eulerian circuit exists when every vertex has equal in-degree and out-degree. An Eulerian path exists when at most one vertex has out-degree exceeding in-degree by one (the start), and at most one has in-degree exceeding out-degree by one (the end).
def classify_eulerian_directed(graph: dict[int, list[int]]) -> str:
"""
Check Eulerian conditions for directed graph.
Graph: {vertex: [outgoing neighbors]}
"""
in_degree = defaultdict(int)
out_degree = defaultdict(int)
for u, neighbors in graph.items():
out_degree[u] = len(neighbors)
for v in neighbors:
in_degree[v] += 1
all_vertices = set(graph.keys()) | set(in_degree.keys())
start_vertices = 0 # out = in + 1
end_vertices = 0 # in = out + 1
for v in all_vertices:
diff = out_degree[v] - in_degree[v]
if diff == 0:
continue
elif diff == 1:
start_vertices += 1
elif diff == -1:
end_vertices += 1
else:
return "none"
if start_vertices == 0 and end_vertices == 0:
return "circuit"
elif start_vertices == 1 and end_vertices == 1:
return "path"
else:
return "none"
The Chinese Postman Problem handles non-Eulerian graphs. When a graph lacks an Eulerian path, we must repeat some edges. The goal is minimizing total repeated edge weight. The solution involves finding minimum-weight matchings between odd-degree vertices—a more complex algorithm but essential for real-world routing where perfect Eulerian conditions rarely exist.
Multigraphs (multiple edges between vertices) work fine with edge-indexed representations. Self-loops contribute 2 to a vertex’s degree, maintaining the even/odd counting logic.
Eulerian problems exemplify elegant algorithm design: simple existence conditions, efficient solutions, and broad practical applications. Master Hierholzer’s algorithm, understand the degree conditions, and you’ll recognize these problems in domains from biology to logistics.