---
title: Eulerian Tours
module: Graphs
moduleNumber: 6
lessonNumber: 13
order: 613
summary: |
  An **Eulerian tour** uses every _edge_ of a graph exactly once. We give the
  exact parity and balance conditions under which one exists (even degree
  for undirected graphs, in-degree equal to out-degree for directed) and Hierholzer's
  $O(E)$ algorithm that constructs one by splicing closed sub-tours. We contrast
  this sharply with the **Hamiltonian** problem (visit every _vertex_ once),
  which is NP-complete: visiting edges is easy, visiting vertices is hard.
topics: [Graphs]
sources:
  - book: Skiena
    ref: "§ — Eulerian Cycles"
  - book: Erickson
    ref: "Ch. — Graph Traversal"
  - book: CLRS
    ref: "Ch. — Euler Tour (Problem)"
practice:
  - title: 'Reconstruct Itinerary'
    slug: reconstruct-itinerary
    difficulty: Hard
  - title: 'Valid Arrangement of Pairs'
    slug: valid-arrangement-of-pairs
    difficulty: Hard
  - title: 'Cracking the Safe'
    slug: cracking-the-safe
    difficulty: Hard
---

The traversals of the previous lessons were about _reaching_ vertices: BFS and
[DFS](/algorithms/graphs/representations-and-traversal) each touch every vertex
once and impose no constraint on how often an edge is
used. This lesson inverts the constraint. 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.

> **Definition.** An **Eulerian path** is a walk that uses every edge of the
> graph _exactly once_. An **Eulerian circuit** (or _Eulerian tour_) is an
> Eulerian path that starts and ends at the same vertex — a _closed_ one.

One contrast is central. 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 their complexities are far apart. 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 $\textsf{P}$ vs
$\textsf{NP}$ (we return to intractability in a later module).[^erickson-euler]
In short: **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.

$$
% caption: The parity argument at one vertex: each passage through $v$ pairs an arriving
%          edge with a departing edge, so $\deg(v) = 6$ splits into three passages and an
%          interior vertex always has even degree.
\begin{tikzpicture}[font=\footnotesize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[circle, draw, minimum size=8mm, inner sep=1pt, font=\small] (v) at (0,0) {$v$};
  % passage 1 (solid acc): arrive from 150, leave toward 30
  \draw[->, acc, thick] (150:2.3) -- (v);
  \draw[->, acc, thick] (v) -- (30:2.3);
  \node[font=\scriptsize, text=acc] at (150:2.65) {1};
  \node[font=\scriptsize, text=acc] at (30:2.65) {1};
  % passage 2 (dashed acc): arrive from 90, leave toward -90
  \draw[->, acc, thick, dashed] (90:2.3) -- (v);
  \draw[->, acc, thick, dashed] (v) -- (-90:2.3);
  \node[font=\scriptsize, text=acc] at (90:2.65) {2};
  \node[font=\scriptsize, text=acc] at (-90:2.65) {2};
  % passage 3 (muted): arrive from -150, leave toward -30
  \draw[->, black, thick] (-150:2.3) -- (v);
  \draw[->, black, thick] (v) -- (-30:2.3);
  \node[font=\scriptsize, text=black] at (-150:2.65) {3};
  \node[font=\scriptsize, text=black] at (-30:2.65) {3};
  \node[draw=none, font=\scriptsize] at (0,-3.2) {$\deg v = 6$: three passages, three pairs};
\end{tikzpicture}
$$

> **Theorem (undirected).** Let $G$ be connected when isolated vertices are
> ignored. Then $G$ has an **Eulerian circuit** iff _every_ vertex has **even
> degree**. It has an **Eulerian path** (open) iff **exactly $0$ or $2$**
> vertices have **odd degree**; when there are two, they are the only possible
> endpoints.

The degree count is a decision test — _does a tour exist?_ — so the iff is the two
guarantees from [the foundations](/algorithms/foundations/what-is-an-algorithm) at
work. **Necessity** (every Eulerian graph satisfies the parity condition) is
**completeness**: no graph that admits a tour is rejected by the test.
**Sufficiency** — that the condition guarantees a tour — is **soundness**: when the
test passes, Hierholzer's algorithm below produces an actual tour, so the "yes" is
never empty. The witness _is_ the proof of sufficiency.

> **Proof sketch (necessity).** Fix the tour and a vertex $v$. Each passage through
> $v$ uses two of its incident edges. If the tour is closed, _every_ visit to $v$,
> including the start, where it leaves and later returns, is a through-passage, so
> $\deg(v)$ is even for all $v$. If the tour is open, the same pairing holds at
> every vertex _except_ the two endpoints, where one unpaired edge (the very first
> departure, the very last arrival) leaves an odd count. Hence at most two odd
> vertices, and a hand-shaking count forces the number of odd-degree vertices to be
> even, so it is $0$ or $2$.[^skiena-euler] $\qed$

> **Proof sketch (sufficiency).** Suppose every degree is even and the edges are
> connected. Start anywhere and walk greedily along unused edges. Arriving at any
> vertex $w$ other than the start, the walk has so far consumed an _odd_ number of
> edges at $w$ (a pair per earlier passage, plus the edge it just arrived on), so
> by evenness an unused edge remains and the walk can leave. The only place it can
> get stuck is the start — the walk always terminates as a _closed_ sub-tour $T$.
> If $T$ misses some edge, connectivity supplies a missed edge incident to a vertex
> $u$ on $T$ (follow any path from a missed edge toward $T$; the first vertex of
> $T$ it touches works). The unused edges still have all-even degrees, since $T$
> removed pairs everywhere, so the same greedy walk from $u$ over unused edges
> yields a second closed sub-tour, which splices into $T$ at $u$. Each splice
> consumes at least one edge, so finitely many splices exhaust the graph, and the
> result is a single closed tour using every edge once. For the open case with two
> odd vertices $x, y$: add a virtual edge $xy$, making all degrees even; the
> resulting circuit, cut at the virtual edge, is an Eulerian path from $x$ to $y$.
> $\qed$

This argument, followed carefully, is already Hierholzer's algorithm, made
concrete below.

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.

> **Theorem (directed).** Let the edges of $G$ form a single connected component
> (every vertex with an edge is reachable in the underlying undirected sense).
> Then $G$ has an **Eulerian circuit** iff every vertex has
> $\text{in-deg}(v) = \text{out-deg}(v)$. It has an **Eulerian path** iff exactly
> one vertex has $\text{out-deg} - \text{in-deg} = +1$ (the **start**), exactly
> one has $\text{in-deg} - \text{out-deg} = +1$ (the **end**), and every other
> vertex is balanced.

> **Proof sketch (necessity).** 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 (one incoming, one outgoing
> per passage). $\qed$

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.

$$
% caption: directed path: start $s$ has $\text{out}-\text{in}=+1$, end $t$ has
%          $\text{in}-\text{out}=+1$, $a,b$ balanced
\begin{tikzpicture}[
  >=stealth,
  every node/.style={circle, draw, minimum size=8mm, inner sep=1pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw=acc, thick, text=acc] (s) at (0,0)   {$s$};
  \node (a) at (2.0,0)  {$a$};
  \node (b) at (4.0,0.9) {$b$};
  \node[draw=acc, thick, text=acc] (t) at (4.0,-0.9) {$t$};
  \draw[->] (s) -- (a);
  \draw[->] (a) to[bend left=30] (b);
  \draw[->] (b) to[bend left=30] (a);
  \draw[->] (a) -- (t);
  \node[draw=none, font=\footnotesize, text=acc] at (0,-1.0) {$+1$ out};
  \node[draw=none, font=\footnotesize, text=acc] at (4.9,-0.9) {$+1$ in};
\end{tikzpicture}
$$

$$
% caption: balanced but disconnected: two separate even loops admit no single Eulerian
%          tour
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (a) at (0,1.2) {$a$};
  \node (b) at (1.2,0) {$b$};
  \node (c) at (0,-1.2) {$c$};
  \draw (a)--(b)--(c)--(a);
  \node (d) at (3.4,1.2) {$d$};
  \node (e) at (4.6,0) {$e$};
  \node (f) at (3.4,-1.2) {$f$};
  \draw[acc, thick] (d)--(e)--(f)--(d);
  \node[draw=none, font=\footnotesize] at (0.4,-2.1) {even};
  \node[draw=none, font=\footnotesize, text=acc] at (3.8,-2.1) {even, but disjoin\/t};
\end{tikzpicture}
$$

$$
% caption: Eulerian path $\iff$ 0 or 2 odd-degree vertices
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=8mm, inner sep=1pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \tikzset{odd/.style={circle, draw=acc, very thick, text=acc, minimum size=8mm, inner sep=1pt, font=\small}}
  \tikzset{edgelbl/.style={draw=none, fill=none, font=\footnotesize, text=acc}}
  \node[odd] (a) at (0,0) {$a$};
  \node (b) at (2.4,1.1) {$b$};
  \node (c) at (4.8,0) {$c$};
  \node[odd] (d) at (2.4,-1.6) {$d$};
  % degree labels
  \node[draw=none] at (-0.95,0.0) {\scriptsize$\deg 3$};
  \node[draw=none] at (2.4,1.95) {\scriptsize$\deg 2$};
  \node[draw=none] at (5.75,0.0) {\scriptsize$\deg 2$};
  \node[draw=none] at (2.4,-2.45) {\scriptsize$\deg 3$};
  % edges numbered in traversal order a-b-c-d-a-d (path a..d)
  \draw[->] (a) -- node[edgelbl, above left]{1} (b);
  \draw[->] (b) -- node[edgelbl, above right]{2} (c);
  \draw[->] (c) -- node[edgelbl, right]{3} (d);
  \draw[->] (d) to[bend left=22] node[edgelbl, below left]{4} (a);
  \draw[->] (a) to[bend left=22] node[edgelbl, above right]{5} (d);
\end{tikzpicture}
$$

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$.

::impl{algo="eulerian_tour#analyze"}

## Hierholzer's algorithm

The natural greedy idea is _almost_ right: start somewhere and keep walking along
unused edges. 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 covered _every_ edge. **Hierholzer's algorithm** fixes
this with one 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.

> **Intuition.** A closed walk through a balanced vertex always uses its edges in
> pairs, so an unused edge at a visited vertex $u$ implies an _even_ number of
> unused edges at $u$ — enough to walk out and circle back to $u$. That returning
> loop is another closed sub-tour, and it can be **spliced** into the route
> exactly at $u$. Splicing never breaks closure, and every splice consumes at
> least one fresh edge, so the process halts having consumed them all.

$$
% caption: merge closed sub-tours into one Eulerian circuit
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=1pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % main closed walk: s - p - q - s   (splice point u = p)
  \node (s) at (0,0) {$s$};
  \node (p) at (2.0,1.0) {$u$};
  \node (q) at (2.0,-1.0) {$q$};
  \draw[->] (s) -- (p);
  \draw[->] (p) -- (q);
  \draw[->] (q) -- (s);
  % spliced-in closed sub-tour at u (in acc): u - x - y - u
  \node[draw=acc, very thick, text=acc] (x) at (4.4,1.9) {$x$};
  \node[draw=acc, very thick, text=acc] (y) at (4.4,0.1) {$y$};
  \draw[->, draw=acc, very thick] (p) -- (x);
  \draw[->, draw=acc, very thick] (x) -- (y);
  \draw[->, draw=acc, very thick] (y) -- (p);
  \node[draw=none, rectangle, text=acc, font=\footnotesize] at (2.0,2.55) {splice at $u$};
\end{tikzpicture}
$$

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$.

### Splice by splice on a concrete graph

We trace the splicing in full on a small graph. Take
seven vertices $a, \dots, g$ and nine edges: a central triangle $a b c$, a second
triangle $c d e$ hanging off $c$, and a third triangle $b f g$ hanging off $b$.
Every degree is even ($a, d, e, f, g$ have degree $2$; $b$ and $c$ have degree
$4$), the graph is connected, so an Eulerian circuit exists. Adjacency lists are
kept in alphabetical order, and we start at $a$.

**Loop 1.** The greedy walk from $a$ picks $b$ (first neighbor), then $b$ picks
$c$ (its edge to $a$ is used), then $c$ picks $a$. The walk is stuck at $a$ (both
of $a$'s edges are gone), having closed the sub-tour $a \to b \to c \to a$ after
only three of the nine edges.

**Loop 2, spliced at $c$.** Vertex $c$ sits on the tour with two unused edges. The
greedy walk from $c$ over unused edges gives $c \to d \to e \to c$, and inserting
it where the tour visits $c$ stretches the route to
$a \to b \to \underline{c \to d \to e \to c} \to a$, six edges.

$$
% caption: Splices one and two: the walk from $a$ closes loop 1 ($a b c a$, left);
%          vertex $c$ still has unused edges, so loop 2 ($c d e c$) is walked and
%          spliced in at $c$ (right), stretching the route to $a\,b\,c\,d\,e\,c\,a$.
%          The triangle at $b$ is still untouched.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6.5mm, inner sep=1pt, font=\small},
  lbl/.style={draw=none, fill=none, font=\scriptsize, text=acc},
  pcap/.style={draw=none, fill=none, font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % ---- panel 1: loop 1 ----
  \begin{scope}
    \node (a) at (0,0) {$a$};
    \node (b) at (2.0,0) {$b$};
    \node (c) at (1.0,1.5) {$c$};
    \node (d) at (0.2,2.9) {$d$};
    \node (e) at (1.8,2.9) {$e$};
    \node (f) at (3.4,1.1) {$f$};
    \node (g) at (3.4,-1.1) {$g$};
    % unused edges muted
    \draw[black] (c)--(d); \draw[black] (d)--(e); \draw[black] (e)--(c);
    \draw[black] (b)--(f); \draw[black] (f)--(g); \draw[black] (g)--(b);
    % loop 1 in acc with order labels
    \draw[->, acc, thick] (a) -- (b);
    \draw[->, acc, thick] (b) -- (c);
    \draw[->, acc, thick] (c) -- (a);
    \node[lbl] at (1.0,-0.42) {1};
    \node[lbl] at (1.82,0.95) {2};
    \node[lbl] at (0.18,0.95) {3};
    \node[pcap] at (1.7,-1.9) {loop 1 returns to $a$};
  \end{scope}
  % ---- panel 2: splice at c ----
  \begin{scope}[xshift=64mm]
    \node (a) at (0,0) {$a$};
    \node (b) at (2.0,0) {$b$};
    \node (c) at (1.0,1.5) {$c$};
    \node (d) at (0.2,2.9) {$d$};
    \node (e) at (1.8,2.9) {$e$};
    \node (f) at (3.4,1.1) {$f$};
    \node (g) at (3.4,-1.1) {$g$};
    \draw[black] (b)--(f); \draw[black] (f)--(g); \draw[black] (g)--(b);
    \draw[->, acc, thick] (a) -- (b);
    \draw[->, acc, thick] (b) -- (c);
    % spliced loop dashed
    \draw[->, acc, thick, dashed] (c) -- (d);
    \draw[->, acc, thick, dashed] (d) -- (e);
    \draw[->, acc, thick, dashed] (e) -- (c);
    \draw[->, acc, thick] (c) -- (a);
    \node[lbl] at (1.0,-0.42) {1};
    \node[lbl] at (1.82,0.95) {2};
    \node[lbl] at (0.2,2.1) {3};
    \node[lbl] at (1.0,3.28) {4};
    \node[lbl] at (1.82,2.3) {5};
    \node[lbl] at (0.18,0.95) {6};
    \node[pcap] at (1.7,-1.9) {loop 2 spliced in at $c$};
  \end{scope}
\end{tikzpicture}
$$

**Loop 3, spliced at $b$.** One vertex on the route still has unused edges: $b$,
with the untouched triangle $b f g$. Walking it gives $b \to f \to g \to b$, and
splicing at $b$ produces the full nine-edge circuit:

$$
a \;\to\; \underline{b \to f \to g \to b} \;\to\; c \to d \to e \to c \;\to\; a.
$$

$$
% caption: The completed circuit after splicing loop 3 ($b f g b$, dashed) in at $b$:
%          nine edges numbered in f\/inal traversal order
%          $a\,b\,f\,g\,b\,c\,d\,e\,c\,a$. Splicing renumbers everything after the
%          insertion point.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6.5mm, inner sep=1pt, font=\small},
  lbl/.style={draw=none, fill=none, font=\scriptsize, text=acc},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (a) at (0,0) {$a$};
  \node (b) at (2.0,0) {$b$};
  \node (c) at (1.0,1.5) {$c$};
  \node (d) at (0.2,2.9) {$d$};
  \node (e) at (1.8,2.9) {$e$};
  \node (f) at (3.4,1.1) {$f$};
  \node (g) at (3.4,-1.1) {$g$};
  \draw[->, acc, thick] (a) -- (b);
  \draw[->, acc, thick, dashed] (b) -- (f);
  \draw[->, acc, thick, dashed] (f) -- (g);
  \draw[->, acc, thick, dashed] (g) -- (b);
  \draw[->, acc, thick] (b) -- (c);
  \draw[->, acc, thick] (c) -- (d);
  \draw[->, acc, thick] (d) -- (e);
  \draw[->, acc, thick] (e) -- (c);
  \draw[->, acc, thick] (c) -- (a);
  \node[lbl] at (1.0,-0.42) {1};
  \node[lbl] at (2.42,0.95) {2};
  \node[lbl] at (3.78,0) {3};
  \node[lbl] at (2.42,-0.95) {4};
  \node[lbl] at (1.82,0.95) {5};
  \node[lbl] at (0.2,2.1) {6};
  \node[lbl] at (1.0,3.28) {7};
  \node[lbl] at (1.82,2.3) {8};
  \node[lbl] at (0.18,0.95) {9};
\end{tikzpicture}
$$

Two things to observe. Splicing is _insertion_, so every edge after the splice
point gets renumbered; the tour is best kept in a linked structure or, as next,
emitted in reverse by a stack. And the splice points ($c$, then $b$) were found
_on the existing route_, which is where the connectivity hypothesis is used:
any unused edge is linked to the route through the graph, so some route
vertex always offers a way in.

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.

```algorithm
caption: $\textsc{Hierholzer}(G, s)$ — build an Eulerian tour from start $s$ in $O(E)$
for each vertex $v$ do
  $ptr[v] \gets 0$            // next-unused-edge index
$stack \gets [\,s\,]$;\ \ \ $route \gets [\,]$
while $stack$ is nonempty do
  $u \gets stack.\text{top}()$
  if $ptr[u] < |adj[u]|$ then          // u has an unused edge
    $w \gets adj[u][\,ptr[u]\,]$
    $ptr[u] \gets ptr[u] + 1$          // consume edge u→w
    $stack.\text{push}(w)$             // walk forward
  else                                 // u exhausted: back out
    $route.\text{append}(stack.\text{pop}())$
$\textbf{return } reverse(route)$       // emitted in reverse on backtrack
```

> **Correctness.** 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. $\qed$

### The stack in action

Running the pseudocode on the seven-vertex graph above shows how the stack
performs the three splices without ever representing them explicitly. Pushes walk
forward along unused edges; a pop means the top vertex is exhausted and joins the
output. Reading top-of-stack as the walk's current position:

| step | action | stack (bottom $\to$ top) | $route$ so far |
|---|---|---|---|
| 1 | push $b, c, a$: walk $a \to b \to c \to a$, then $a$ is exhausted | $a\; b\; c\; a$ | — |
| 2 | pop $a$ | $a\; b\; c$ | $a$ |
| 3 | $c$ resumes its list: push $d, e, c$ (loop $c \to d \to e \to c$) | $a\; b\; c\; d\; e\; c$ | $a$ |
| 4 | pop $c, e, d, c$: the whole $cde$ loop is exhausted | $a\; b$ | $a\; c\; e\; d\; c$ |
| 5 | $b$ resumes: push $f, g, b$ (loop $b \to f \to g \to b$) | $a\; b\; f\; g\; b$ | $a\; c\; e\; d\; c$ |
| 6 | pop $b, g, f, b, a$: everything drains | — | $a\; c\; e\; d\; c\; b\; g\; f\; b\; a$ |

Reversing the final $route$ gives $a\, b\, f\, g\, b\, c\, d\, e\, c\, a$ —
exactly the circuit from the figure, with both splices threaded through their
splice vertices. The mechanism: a vertex is only popped once its edges are gone,
so anything discovered _later_ from a resumed vertex (steps 3 and 5) is appended
to $route$ _earlier_, and the reversal slots each sub-tour into the route at the
right place. Step 3 is the splice at $c$; step 5 is the splice at $b$; neither
required touching the part of the route already emitted.

The per-vertex pointer $ptr[v]$ is what "resumes its list" means: when $c$
reappears at the top of the stack in step 3, it continues scanning its adjacency
list from where it stopped, not from the beginning. In an undirected graph the
pointer alone is not quite enough: the edge $\{b, c\}$ consumed from $b$'s side
must also be dead when scanned from $c$'s side — so each undirected edge carries
an id and a $used$ bit, and the scan skips ids already marked.

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).[^clrs-euler]

::impl{algo="eulerian_tour#hierholzer+is_eulerian_tour"}

## Path versus circuit

The circuit and the open path differ only in bookkeeping, but the bookkeeping
trips people up, so we spell it out.

- **Start vertex.** For a circuit, any vertex with an edge works, since the tour
  is cyclic and can be rotated to begin anywhere. For an open path the start is
  _forced_: an odd-degree vertex (undirected) or the unique vertex with
  $\text{out} - \text{in} = +1$ (directed). Starting Hierholzer at a balanced
  vertex when two odd vertices exist produces a walk that gets stuck somewhere
  other than its start, and the stack output is not a valid path.
- **The virtual-edge reduction.** The path case reduces to the circuit case: join
  the two odd vertices $x, y$ by a temporary edge (directed: add $t \to s$ from
  the end-excess vertex to the start-excess one). All degrees become even
  (balanced), run the circuit algorithm, then delete the virtual edge from the
  resulting cyclic tour — the circuit breaks at exactly that point into an
  Eulerian path from $x$ to $y$. This is often cleaner than special-casing the
  start, and it is the proof of the path half of the existence theorem.
- **Zero odd vertices still allows an open path.** A graph whose vertices are all
  even has an Eulerian circuit, and any circuit read from any starting point is
  also an Eulerian path. "Exactly $0$ or $2$ odd vertices" in the theorem covers
  both.

## Pitfalls

- **Quadratic edge deletion.** The textbook description says "walk along an edge
  and delete it." Deleting from the middle of an adjacency list by scanning costs
  degree-of-$v$ per step, and a high-degree hub turns the whole run into
  $O(E^2)$ — on a star-like multigraph with $E$ parallel edges this is the
  difference between milliseconds and minutes. To address this, use the per-vertex
  pointer $ptr[v]$ from the pseudocode: each list is scanned once, left to right, never
  compacted. Undirected graphs additionally need the shared-edge $used$ bit so the
  twin copy is skipped in $O(1)$ when the pointer reaches it.
- **Connectivity over the wrong vertex set.** The correct hypothesis is that the
  _edges_ form one connected component; vertices with no edges at all are
  irrelevant. A connectivity check run over all of $V$ rejects valid inputs, e.g.
  an airport list where some airports appear in no ticket. Run
  [DFS](/algorithms/graphs/representations-and-traversal) from any endpoint of any
  edge and demand that it reach every vertex _of nonzero degree_.
- **Degrees balance, edges do not connect.** The converse trap: two disjoint even
  cycles pass every degree test yet admit no single tour (the figure in the
  existence section). Both halves of the test are necessary; skipping the
  connectivity half is a classic wrong-answer-on-hidden-tests bug.
- **Parallel edges and self-loops are legal.** Eulerian theory applies to
  multigraphs — Königsberg itself has parallel bridges. Representations keyed on
  vertex pairs (a set of `(u, v)` tuples, or an adjacency _matrix_) silently merge
  parallel edges; store edge _ids_ in the adjacency lists instead. A self-loop
  adds $2$ to its vertex's degree and never breaks parity.
- **Recursion depth.** The recursive formulation of Hierholzer recurses once per
  edge; at $E = 10^5$ that overflows default stacks in most languages. The
  explicit-stack version above is the same algorithm without that failure mode.

## 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 standout application: 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.

Consider the smallest case. 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:

$$
% caption: The $k=2$ binary de Bruijn graph (vertices $0,1$; edges = the four $2$-grams).
%          Its Eulerian circuit $00,01,11,10$ spells the cyclic de Bruijn sequence $0011$.
\begin{tikzpicture}[>=Stealth, font=\small,
  V/.style={circle, draw, minimum size=9mm, font=\small},
  e/.style={->, line width=1pt},
  lbl/.style={font=\scriptsize, fill=white, inner sep=1.5pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[V] (z) at (0,0) {$0$};
  \node[V] (o) at (3.2,0) {$1$};
  % self-loops
  \draw[e] (z) to[out=160, in=200, looseness=8] node[lbl, left]{$00$} (z);
  \draw[e] (o) to[out=-20, in=20, looseness=8] node[lbl, right]{$11$} (o);
  % cross edges
  \draw[e] (z) to[bend left=22] node[lbl, above]{$01$} (o);
  \draw[e] (o) to[bend left=22] node[lbl, below]{$10$} (z);
  \node[font=\scriptsize, acc] at (1.6,-1.7)
    {circuit 00, 01, 11, 10 spells 0011};
\end{tikzpicture}
$$

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 intractable.

::impl{algo="reconstruct_itinerary,de_bruijn_sequence"}

## 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.
- **Path from circuit**: join the two odd (or imbalanced) vertices by a virtual
  edge, build the circuit, cut it at that edge. **Pitfalls**: never delete edges
  by scanning (use pointers plus a shared $used$ bit), store edge ids so parallel
  edges survive, and check connectivity over nonzero-degree vertices only.
- **Applications**: itinerary reconstruction (lexicographic via sorted edges),
  **de Bruijn sequences** (Eulerian circuit on the de Bruijn graph), and DNA
  fragment assembly.

[^erickson-euler]: **Erickson**, Ch. — Graph Traversal: Eulerian tours via the degree characterization, contrasted with the NP-complete Hamiltonian problem.
[^skiena-euler]: **Skiena**, § — Eulerian Cycles: the even-degree (balanced) existence condition and its parity proof.
[^clrs-euler]: **CLRS**, Ch. — Euler Tour (Problem): linear-time construction of an Eulerian tour on a graph satisfying the degree/balance conditions.