2.2 Eulerian Circuits

In graph theory, the concept of traversing a network without retracing edges emerged from one of the most famous problems in mathematical history: the Seven Bridges of Königsberg. In 1736, Leonhard Euler proved that no such walk existed for the city's bridges, thereby founding graph theory as a formal discipline. Today, the structures he described—Eulerian trails and Eulerian circuits—form the backbone of network routing, bioinformatics, and optimization algorithms.

Key Definitions

Unlike Hamiltonian paths, which visit every vertex exactly once and are NP-complete to find, Eulerian circuits can be detected and constructed in linear time, provided the graph satisfies specific degree conditions.

Euler's Theorem

The existence of Eulerian trails and circuits is completely characterized by the degrees of the graph's vertices. This elegant result, first proved by Euler in 1736, states:

Corollary: The sum of degrees in any finite graph is always even (Handshaking Lemma). Therefore, the number of odd-degree vertices must be even, which is why an Eulerian trail can only exist when there are exactly 0 or 2 odd-degree vertices.

Proof Intuition & Graph Traversal

The proof relies on analyzing vertex entries and exits during a walk:

• Each time the walk passes through a vertex (without starting or ending there), it uses two edges: one to enter, one to exit.
• Therefore, internal vertices in any closed walk must have even degree.
• If exactly two vertices have odd degree, the walk must start at one and end at the other, using the "extra" edge at each endpoint.

This local degree condition is both necessary and sufficient because a connected graph with all even degrees can be decomposed into disjoint cycles, which can be spliced together to form a single Eulerian circuit.

Hierholzer's Algorithm

Discovered by Carl Hierholzer in 1873, this algorithm efficiently constructs an Eulerian circuit in O(|E|) time. The core idea is simple: find any cycle, then recursively splice in remaining edges.

function HierholzersAlgorithm(G):
    // Assumes G is connected and all vertices have even degree
    stack ← [start_vertex]
    circuit ← []

    while stack not empty:
        v ← stack.top()
        if degree(v) > 0:
            u ← pick_adjacent(v)
            remove_edge(v, u)
            stack.push(u)
        else:
            circuit.append(stack.pop())

    return reverse(circuit)

Why it works: The stack-based approach naturally handles cycle splicing. When a vertex is exhausted (degree becomes 0), it's added to the circuit. Because all vertices start with even degree, any closed cycle can be merged with the main path without breaking connectivity, guaranteeing a valid Eulerian circuit in linear time.

Real-World Applications

• Network Routing & Inspection: Designing patrol routes, street sweeping schedules, and mail delivery paths where every street segment must be covered exactly once.
• DNA Sequencing: De Bruijn graphs in next-generation sequencing use Eulerian paths to reconstruct genomes from short overlapping fragments.
• VLSI Circuit Design: Testing and verifying complete edge coverage in integrated circuit layouts.
• Puzzle & Game Theory: Solving "one-stroke" drawing puzzles (e.g., Chinese Postman Problem variants, Etch-A-Sketch patterns).