Eulerian Tours

The traversals of the previous lessons were about reaching vertices: BFS and DFS each touch every vertex once and impose no constraint on how often an edge is used. This lesson turns the question inside out. We ask for a walk that crosses every edge exactly once: the problem Euler posed in 1736 for the seven bridges of Königsberg, and the historical seed of graph theory itself. Unlike most use everything exactly once problems, this one has a clean local characterization and a linear-time algorithm.

It is worth fixing the contrast that gives the lesson its shape. An Eulerian tour constrains edges; its near-twin, the Hamiltonian tour, constrains vertices, visiting every vertex exactly once. The two look like mirror images, but they sit on opposite sides of the great divide in algorithms. Deciding whether an Eulerian tour exists, and building one, takes $O(E)$ time, as we will see. Deciding whether a Hamiltonian cycle exists is NP-complete: no polynomial algorithm is known, and finding one would settle $\text{P}$ vs $\text{NP}$ (we return to intractability in a later module).¹ The slogan to remember: visiting every edge is easy; visiting every vertex is hard.

When does an Eulerian tour exist?

The existence test is pure local arithmetic on degrees. The intuition is a single parity argument: think of walking through the tour and watching one fixed vertex $v$. Every time the walk passes through $v$ it arrives on one edge and leaves on another, consuming a pair of edges incident to $v$. So the edges at an interior vertex must come in pairs.

For directed graphs the parity condition sharpens into a balance condition, because each edge now has a direction: a through-passage at $v$ consumes one incoming and one outgoing edge.

The two extra-edge vertices are forced: a start emits one more edge than it absorbs, an end absorbs one more than it emits, and everyone the walk merely passes through breaks even. Connectivity is the second, easily-forgotten half of the test: degrees can balance perfectly while the edges split into two disjoint loops, which no single walk can join.

Here $a$ and $d$ each have odd degree $3$; the other two are even, so an Eulerian path exists and must run between $a$ and $d$. The numbering $1,2,3,4,5$ is one valid traversal $a\to b\to c\to d\to a\to d$, which crosses all five edges once and stops at $d$.

Hierholzer's algorithm

The natural greedy idea is almost right: start somewhere, keep walking along edges you have not used, and never look back. Because every vertex is balanced (or you begin at an odd endpoint), you can always leave a vertex you entered, so the walk only ever gets stuck back at its starting vertex, closing a loop. But that first loop may not have swallowed every edge. Hierholzer's algorithm fixes this with one elegant move: whenever a vertex on the current tour still has unused edges hanging off it, splice a fresh closed sub-tour in at that vertex, and repeat until nothing is left over.

The blue loop $u\to x\to y\to u$ is a closed sub-tour discovered when the main walk $s\to u\to q\to s$ reached $u$ and found unused edges. Inserting it at $u$ yields the single circuit $s\to u\to x\to y\to u\to q\to s$.

The clean implementation does the splicing implicitly with a stack and one edge pointer per vertex (so each vertex resumes scanning where it left off, never re-examining a used edge). We push our way forward along unused edges; when a vertex runs dry, we pop it onto the output. The route is therefore emitted in reverse on backtracking, and a spliced sub-tour is naturally inserted at its shared vertex.

Why it consumes every edge. Each iteration either advances an edge pointer (consuming exactly one edge) or pops one vertex; both can happen at most $O(E)$ and $O(V)$ times respectively, so the loop runs in $O(V+E)=O(E)$ on a connected graph. The pointer trick means each edge is examined once, never rescanned. When a vertex $u$ is finally popped, the algorithm has, by the parity argument, already drained every edge incident to $u$ along the way; any edge it had skipped would have been picked up by a later pointer advance before $u$ could exhaust. Reading $route$ in reverse threads every discovered sub-tour through its splice vertex, producing one walk that uses all $E$ edges exactly once. If the existence conditions hold, the output is a valid Eulerian tour; for an open Eulerian path, start $s$ at the unique out-excess vertex (directed) or an odd-degree vertex (undirected).³

Applications

The pattern use every edge once is more common than it first appears. Reconstruct Itinerary asks for a flight schedule that uses every ticket exactly once: an Eulerian path on the directed multigraph of airports, where the problem's lexicographically-smallest requirement is met by keeping each vertex's outgoing destinations in sorted order and letting Hierholzer consume them in that order. De Bruijn sequences are the gem: to find a shortest cyclic string containing every length-$k$ string over an alphabet exactly once (the Cracking the Safe problem), build the de Bruijn graph whose vertices are $(k-1)$-grams and whose edges are $k$-grams; that graph is balanced by construction, so an Eulerian circuit spells out the optimal sequence.

The smallest case makes it vivid. For binary strings of length $k=2$, the de Bruijn graph has two vertices, the $1$-grams $0$ and $1$, and four edges, the $2$-grams $00,01,10,11$. Every vertex is balanced (in-degree $=$ out-degree $=2$), so an Eulerian circuit exists; following $00\to 01\to 11\to 10$ and reading the new symbol off each edge spells the de Bruijn sequence $0011$, a length-$4$ cyclic string in which all four $2$-bit patterns appear exactly once:

The same idea drives DNA fragment assembly, where overlapping reads become edges of a de Bruijn graph and an Eulerian path stitches the genome back together, a problem that, posed instead as a Hamiltonian path over the reads, would be hopeless.

Takeaways

• An Eulerian path uses every edge exactly once; an Eulerian circuit is a closed one. This is the easy cousin of the Hamiltonian tour (every vertex once), which is NP-complete — edges are easy, vertices are hard.
• Undirected existence: a connected graph has an Eulerian circuit iff every vertex has even degree, and an Eulerian path iff exactly $0$ or $2$ vertices have odd degree (the two odds are the endpoints). The parity argument: each through-visit consumes a pair of incident edges.
• Directed existence: an Eulerian circuit iff $\text{in-deg}=\text{out-deg}$ everywhere; an Eulerian path iff one vertex has $\text{out}-\text{in}=+1$ (start), one has $\text{in}-\text{out}=+1$ (end), rest balanced — plus connectivity of the edge set.
• Hierholzer's algorithm builds a tour in $O(E)$ by walking until it closes a sub-tour, then splicing in further closed sub-tours at vertices with leftover edges; a stack plus a per-vertex edge pointer emits the route in reverse on backtrack.
• Applications: itinerary reconstruction (lexicographic via sorted edges), de Bruijn sequences (Eulerian circuit on the de Bruijn graph), and DNA fragment assembly.