Eulerian Paths and Circuits

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. What Is an Eulerian Trail?

An Eulerian trail (also called an Euler path) is a route through a graph that uses every edge exactly once. You may pass through the same vertex many times, but you are never allowed to travel along the same edge twice.

It answers a surprisingly practical question: given a network of roads, pipes, or cables, can I traverse all of them without ever repeating a connection?

2. Euler Trail vs Euler Circuit

The two terms are closely related but not identical:

• An Eulerian trail uses every edge once and may start and end at different vertices.
• An Eulerian circuit (or Euler cycle) is a closed Eulerian trail, it uses every edge once and returns to its starting vertex.

Every Eulerian circuit is also an Eulerian trail, but the reverse is not true. Which one a graph supports depends entirely on the degrees of its vertices.

3. The Seven Bridges of Königsberg

The Prussian city of Königsberg was split by a river into four landmasses, joined by seven bridges. Citizens wondered whether they could take a walk that crossed every bridge exactly once and returned to the start.

In 1736, Leonhard Euler proved that no such walk exists. He modeled each landmass as a vertex and each bridge as an edge, then observed something decisive: every time you enter a landmass over one bridge, you must leave it over another, so every "pass-through" vertex needs an even number of bridges. All four of Königsberg's vertices had an odd number of bridges, making the walk impossible. This proof is widely regarded as the birth of graph theory. (See our history of graph theory.)

4. The Degree Rule: When Does One Exist?

The degree of a vertex is the number of edges touching it. Euler's insight gives simple, exact rules for a connected graph:

• An Eulerian circuit exists if and only if every vertex has even degree.
• An open Eulerian trail exists if and only if exactly two vertices have odd degree, and the trail must start at one and end at the other.
• If more than two vertices have odd degree, no Eulerian trail exists.

The graph must also be connected. Otherwise, just count the odd-degree vertices and you have your answer.

5. Finding One: Fleury's and Hierholzer's Algorithms

Once you know a trail exists, two classic algorithms construct it:

Build a trail yourself in the Eulerian path visualizer.

Fleury's Algorithm

Walk the graph one edge at a time, and never cross a bridge (an edge whose removal would disconnect the graph) unless you have no other choice. It is easy to understand, but constantly checking for bridges makes it relatively slow.

Hierholzer's Algorithm

The efficient choice, running in O(E) time. Follow edges to form a closed loop, then repeatedly find a vertex on your current path that still has unused edges and splice in another loop there. When no unused edges remain, the loops merge into a single Eulerian circuit.

Hierholzer in Python

The whole algorithm is a stack and a loop. Follow unused edges until you get stuck, pop the stuck vertex onto the answer, then carry on from the vertex beneath it. Every edge is consumed exactly once, which is where the O(E) comes from.

def hierholzer(graph, start):
    """Return an Eulerian trail or circuit as a list of vertices.

    graph maps each vertex to a list of neighbours. The graph must be
    connected and have either zero or exactly two odd-degree vertices.
    When it has two, start must be one of them.
    """
    # Copy the adjacency lists so we can consume edges destructively
    remaining = {v: list(neighbours) for v, neighbours in graph.items()}
    stack = [start]
    trail = []

    while stack:
        v = stack[-1]
        if remaining[v]:
            # Follow any unused edge, deleting it from both endpoints
            u = remaining[v].pop()
            remaining[u].remove(v)
            stack.append(u)
        else:
            # v has no unused edges left, so it belongs here in the trail
            trail.append(stack.pop())

    trail.reverse()
    return trail


def odd_degree_vertices(graph):
    return [v for v, nbrs in graph.items() if len(nbrs) % 2 == 1]


# The Seven Bridges of Konigsberg: four landmasses, seven bridges.
konigsberg = {
    'A': ['B', 'B', 'C', 'C', 'D'],
    'B': ['A', 'A', 'D'],
    'C': ['A', 'A', 'D'],
    'D': ['A', 'B', 'C'],
}
print(odd_degree_vertices(konigsberg))
# ['A', 'B', 'C', 'D'] -> four odd vertices, so Euler's rule says no trail exists

# Remove one of the doubled bridges and exactly two odd vertices remain.
repaired = {
    'A': ['B', 'C', 'C', 'D'],
    'B': ['A', 'D'],
    'C': ['A', 'A', 'D'],
    'D': ['A', 'B', 'C'],
}
print(odd_degree_vertices(repaired))
# ['C', 'D'] -> a trail exists, and it must start at one and end at the other

print(hierholzer(repaired, 'C'))
# ['C', 'D', 'B', 'A', 'C', 'A', 'D'] -> 7 vertices, all 6 edges used exactly once

6. Euler vs Hamiltonian Paths

These two are constantly confused, but they are completely different problems:

The Hamiltonian side has its own tool: the Hamiltonian path solver.

• An Eulerian path visits every edge once.
• A Hamiltonian path visits every vertex once.

The twist is computational: deciding whether an Eulerian trail exists is easy (just count odd degrees), while deciding whether a Hamiltonian path exists is NP-complete, among the hardest problems in computer science. The Traveling Salesperson Problem is a famous Hamiltonian-style challenge.

7. Real-World Applications

• Route inspection (Chinese Postman Problem): finding the shortest route that covers every street, mail delivery, garbage collection, snow plowing, street sweeping.
• DNA sequencing: modern genome assembly builds a de Bruijn graph from short reads and finds an Eulerian path to reconstruct the sequence.
• Network maintenance: inspecting or testing every link in a telecom or utility network exactly once.
• "One-stroke" drawings: the classic puzzle of drawing a figure without lifting your pen is exactly an Eulerian-trail question.