Eulerian Tours · study.

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

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 $P$ vs $NP$ (we return to intractability in a later module).¹ 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.

The parity argument at one vertex: each passage through

v

pairs an arriving edge with a departing edge, so

de g (v) = 6

splits into three passages and an interior vertex always has even degree.

The degree count is a decision test — does a tour exist? — so the iff is the two guarantees from the foundations 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 (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 $x y$ , making all degrees even; the resulting circuit, cut at the virtual edge, is an Eulerian path from $x$ to $y$ . $□$

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.

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.

directed path: start

s

has

out - in = + 1

, end

t

has

in - out = + 1

a, b

balanced

balanced but disconnected: two separate even loops admit no single Eulerian tour

Eulerian path

\leftrightarrow

0 or 2 odd-degree vertices

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

eulerian_tour.pypython

from collections import defaultdict
from collections.abc import Hashable
from typing import Generic, Optional, TypeVar
from graph import Graph


Label = TypeVar("Label", bound=Hashable)


class DegreeProfile(Generic[Label]):
  """
    The in/out (or, undirected, plain) degree summary the existence tests\n
    read. `start` is the forced first vertex of an open path, or None when\n
    the tour is closed and any incident vertex may begin it.\n
  """

  def __init__(
    self,
    has_eulerian_path: bool,
    has_eulerian_circuit: bool,
    start: Optional[Label],
  ) -> None:
    self.has_eulerian_path: bool = has_eulerian_path
    self.has_eulerian_circuit: bool = has_eulerian_circuit
    self.start: Optional[Label] = start

  def __repr__(self) -> str:
    return (
      f"DegreeProfile(path={self.has_eulerian_path}, "
      f"circuit={self.has_eulerian_circuit}, start={self.start!r})"
    )


def _connected_ignoring_isolated(graph: Graph[Label]) -> bool:
  """
    Whether all vertices that carry at least one edge lie in a single\n
    component, treating every edge as undirected. Isolated vertices are\n
    ignored — they place no constraint on an Eulerian tour.\n
  """
  # build an undirected adjacency and record which vertices carry an edge.
  adjacency: dict[Label, list[Label]] = defaultdict(list)
  active: set[Label] = set()
  for vertex in graph.vertices:
    for edge in vertex.outgoing:
      source_label: Label = edge.source.label
      target_label: Label = edge.target.label
      adjacency[source_label].append(target_label)
      adjacency[target_label].append(source_label)
      active.update((source_label, target_label))

  # an edgeless graph is vacuously connected.
  if not active:
    return True

  # flood-fill from any active vertex over the edge set.
  start: Label = next(iter(active))
  seen: set[Label] = {start}
  frontier: list[Label] = [start]
  while frontier:
    current: Label = frontier.pop()
    for neighbor in adjacency[current]:
      if neighbor not in seen:
        seen.add(neighbor)
        frontier.append(neighbor)

  # connected iff the flood reached every edge-bearing vertex.
  return seen == active


def analyze(graph: Graph[Label]) -> DegreeProfile[Label]:
  """
    Decide whether `graph` admits an Eulerian path and/or circuit, and pick\n
    a legal start vertex. Honours `graph.directed`: directed graphs use the\n
    in/out balance condition, undirected graphs use odd-degree parity.\n
    Connectivity of the edge set is required for either to hold.\n
  """
  if not _connected_ignoring_isolated(graph):
    return DegreeProfile(False, False, None)

  if graph.directed:
    return _analyze_directed(graph)
  return _analyze_undirected(graph)


def _analyze_undirected(graph: Graph[Label]) -> DegreeProfile[Label]:
  """
    Undirected test: a circuit exists iff every vertex has even degree; a\n
    path exists iff exactly 0 or 2 vertices have odd degree, and the two\n
    odd vertices are its only possible endpoints.\n
  """
  # collect the odd-degree vertices — the only legal path endpoints.
  odd_vertices: list[Label] = [
    vertex.label for vertex in graph.vertices if len(vertex.outgoing) % 2 == 1
  ]

  # no odd vertices: a circuit; start at any edge-bearing vertex.
  odd_count: int = len(odd_vertices)
  if odd_count == 0:
    first_with_edge: Optional[Label] = next(
      (vertex.label for vertex in graph.vertices if vertex.outgoing), None
    )
    return DegreeProfile(True, True, first_with_edge)

  # exactly two odd vertices: an open path starting at one of them.
  if odd_count == 2:
    return DegreeProfile(True, False, odd_vertices[0])

  return DegreeProfile(False, False, None)


def _analyze_directed(graph: Graph[Label]) -> DegreeProfile[Label]:
  """
    Directed test: a circuit exists iff in-degree equals out-degree at every\n
    vertex; a path exists iff exactly one vertex has out - in = +1 (the\n
    start), exactly one has in - out = +1 (the end), and the rest balance.\n
  """
  # tally in- and out-degree per vertex.
  in_degree: dict[Label, int] = defaultdict(int)
  out_degree: dict[Label, int] = defaultdict(int)
  for vertex in graph.vertices:
    for edge in vertex.outgoing:
      out_degree[edge.source.label] += 1
      in_degree[edge.target.label] += 1

  # a +1 surplus is the path start, -1 the end; anything else fails.
  start_candidates: list[Label] = []
  end_candidates: list[Label] = []
  for vertex in graph.vertices:
    label: Label = vertex.label
    surplus: int = out_degree[label] - in_degree[label]
    if surplus == 1:
      start_candidates.append(label)
    elif surplus == -1:
      end_candidates.append(label)
    elif surplus != 0:
      return DegreeProfile(False, False, None)

  # fully balanced: a circuit; start at any edge-bearing vertex.
  if not start_candidates and not end_candidates:
    first_with_edge = next(
      (vertex.label for vertex in graph.vertices if vertex.outgoing), None
    )
    return DegreeProfile(True, True, first_with_edge)

  # one start and one end: an open path from the surplus-out vertex.
  if len(start_candidates) == 1 and len(end_candidates) == 1:
    return DegreeProfile(True, False, start_candidates[0])

  return DegreeProfile(False, False, None)

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

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.

merge closed sub-tours into one Eulerian circuit

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

Splices one and two: the walk from

a

closes loop 1 (

ab c a

, left); vertex

c

still has unused edges, so loop 2 (

c d ec

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

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 .

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.

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:

\textsc{Hierholzer}(G, s)

— build an Eulerian tour from start

s

O(E)

1
for each vertex $v$ do
2
$ptr[v] \gets 0$
next-unused-edge index
3
$stack \gets [\,s\,]$ ;\ \ \ $route \gets [\,]$
4
while $stack$ is nonempty do
5
$u \gets stack.\text{top}()$
6
if $ptr[u] < |adj[u]|$ then
u has an unused edge
7
$w \gets adj[u][\,ptr[u]\,]$
8
$ptr[u] \gets ptr[u] + 1$
consume edge u→w
9
$stack.\text{push}(w)$
walk forward
10
else
u exhausted: back out
11
$route.\text{append}(stack.\text{pop}())$
12
$\textbf{return } reverse(route)$
emitted in reverse on backtrack

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)	$r o u t e$ 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 $c d e$ 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 $r o u t e$ 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 $r o u t e$ 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 $pt r [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 $u se d$ 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).³

eulerian_tour.pypython

from collections import defaultdict
from collections.abc import Hashable
from typing import Generic, Optional, TypeVar
from graph import Graph


Label = TypeVar("Label", bound=Hashable)


class DegreeProfile(Generic[Label]):
  """
    The in/out (or, undirected, plain) degree summary the existence tests\n
    read. `start` is the forced first vertex of an open path, or None when\n
    the tour is closed and any incident vertex may begin it.\n
  """

  def __init__(
    self,
    has_eulerian_path: bool,
    has_eulerian_circuit: bool,
    start: Optional[Label],
  ) -> None:
    self.has_eulerian_path: bool = has_eulerian_path
    self.has_eulerian_circuit: bool = has_eulerian_circuit
    self.start: Optional[Label] = start

  def __repr__(self) -> str:
    return (
      f"DegreeProfile(path={self.has_eulerian_path}, "
      f"circuit={self.has_eulerian_circuit}, start={self.start!r})"
    )


def hierholzer(
  graph: Graph[Label],
  start: Optional[Label] = None,
) -> Optional[list[Label]]:
  """
    Build an Eulerian tour of `graph` and return it as the sequence of\n
    vertex labels visited, or None when no Eulerian path exists.\n
    The walk has `len(edges) + 1` entries. When `start` is omitted, a legal\n
    start is chosen automatically (the forced endpoint of an open path, or\n
    any edge-bearing vertex for a closed circuit).\n
    Runs in O(E): each edge is consumed exactly once via a per-vertex\n
    pointer, and each vertex is pushed and popped a bounded number of times.\n
  """
  # bail out unless an Eulerian path exists.
  profile: DegreeProfile[Label] = analyze(graph)
  if not profile.has_eulerian_path:
    return None

  # fall back to the analyzer's legal start; no edges means the empty tour.
  if start is None:
    start = profile.start
  if start is None:
    return []

  # Build a half-edge adjacency. Each adjacency entry is (target, edge_id).
  # An undirected edge appears as a pair of half-edges sharing one id, so
  # consuming either half marks the whole edge used via `consumed[edge_id]`;
  # a directed edge gets a unique id and no twin.
  adjacency: dict[Label, list[tuple[Label, int]]] = {
    vertex.label: [] for vertex in graph.vertices
  }
  consumed: list[bool] = []

  if graph.directed:
    for vertex in graph.vertices:
      for edge in vertex.outgoing:
        edge_id: int = len(consumed)
        consumed.append(False)
        adjacency[vertex.label].append((edge.target.label, edge_id))
  else:
    # The shared Graph stores an undirected edge as two outgoing copies
    # (one per endpoint), so pair them under a single id. Visit each
    # unordered endpoint pair once and zip the two directions together —
    # this keeps parallel undirected edges as distinct, separately-consumable
    # edges, which graph.edges() would otherwise collapse.
    seen_pairs: set[frozenset[Label]] = set()
    for vertex in graph.vertices:
      for edge in vertex.outgoing:
        endpoints: frozenset[Label] = frozenset(
          (edge.source.label, edge.target.label)
        )
        if endpoints in seen_pairs:
          continue
        seen_pairs.add(endpoints)
        source_label: Label = edge.source.label
        target_label: Label = edge.target.label
        forward: int = sum(
          1
          for out in graph.vertex(source_label).outgoing
          if out.target.label == target_label
        )
        if source_label == target_label:
          forward //= 2  # a self-loop is listed twice in one outgoing list
        for _ in range(forward):
          edge_id = len(consumed)
          consumed.append(False)
          adjacency[source_label].append((target_label, edge_id))
          if source_label != target_label:
            adjacency[target_label].append((source_label, edge_id))
          else:
            # a self-loop contributes both halves to the same vertex.
            adjacency[source_label].append((target_label, edge_id))

  # per-vertex pointer so a vertex resumes scanning where it left off.
  next_edge: dict[Label, int] = defaultdict(int)
  stack: list[Label] = [start]
  route: list[Label] = []
  while stack:
    current: Label = stack[-1]
    half_edges: list[tuple[Label, int]] = adjacency.get(current, [])
    pointer: int = next_edge[current]

    # skip over half-edges already consumed from the twin side.
    while pointer < len(half_edges) and consumed[half_edges[pointer][1]]:
      pointer += 1
    next_edge[current] = pointer

    if pointer < len(half_edges):
      target, edge_id = half_edges[pointer]
      next_edge[current] = pointer + 1
      consumed[edge_id] = True  # consume the whole edge (both halves)
      stack.append(target)  # walk forward
    else:
      route.append(stack.pop())  # vertex exhausted: emit on backtrack

  route.reverse()
  return route


def is_eulerian_tour(
  graph: Graph[Label],
  tour: list[Label],
) -> bool:
  """
    Verify that `tour` walks `graph` using every edge exactly once. Edges\n
    are matched as a multiset, so parallel edges are handled correctly.\n
  """
  # tally the available half-edges as a directed multiset.
  available: dict[tuple[Label, Label], int] = defaultdict(int)
  half_edge_count: int = 0
  for vertex in graph.vertices:
    for edge in vertex.outgoing:
      available[(edge.source.label, edge.target.label)] += 1
      half_edge_count += 1

  # an undirected edge is stored as two half-edges; a directed one as a single
  # half-edge, so the true edge count differs by a factor of two.
  total_edges: int = half_edge_count if graph.directed else half_edge_count // 2

  # a valid tour visits exactly edge-count + 1 vertices (empty graph: empty).
  if len(tour) != total_edges + 1:
    return len(tour) == 0 and total_edges == 0

  # walk each step, spending its half-edge (and the twin when undirected).
  for step in range(len(tour) - 1):
    move: tuple[Label, Label] = (tour[step], tour[step + 1])
    if available[move] <= 0:
      return False
    available[move] -= 1
    if not graph.directed:
      reverse_move: tuple[Label, Label] = (tour[step + 1], tour[step])
      available[reverse_move] -= 1
  return True

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

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 $out - 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 $pt r [v]$ from the pseudocode: each list is scanned once, left to right, never compacted. Undirected graphs additionally need the shared-edge $u se d$ 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 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 = 1 0^{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:

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

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.

reconstruct_itinerary.pypython

from collections import defaultdict
from typing import Optional, Sequence

def reconstruct_itinerary(
  tickets: Sequence[tuple[str, str]],
  origin: str = "JFK",
) -> Optional[list[str]]:
  """
    The lexicographically smallest itinerary that uses every ticket once and\n
    departs from `origin`, or None when the tickets admit no such route.\n
    Each ticket is a `(from_airport, to_airport)` pair; duplicate tickets are\n
    parallel edges and are honoured.\n
  """
  if not tickets:
    return [origin]

  # destinations per airport, sorted so the smallest is taken first.
  destinations: dict[str, list[str]] = defaultdict(list)
  for departure, arrival in tickets:
    destinations[departure].append(arrival)
  for departure in destinations:
    # reverse-sort so popping from the back yields ascending order cheaply.
    destinations[departure].sort(reverse=True)

  route: list[str] = []
  stack: list[str] = [origin]
  while stack:
    current: str = stack[-1]
    remaining: list[str] = destinations[current]
    if remaining:
      stack.append(remaining.pop())  # walk the smallest unused ticket
    else:
      route.append(stack.pop())  # airport exhausted: emit on backtrack

  route.reverse()

  # a true itinerary spends every ticket; a short walk got stuck early.
  if len(route) != len(tickets) + 1:
    return None

  # tally the ticket multiset so each leg can be checked off as used.
  unused: dict[tuple[str, str], int] = defaultdict(int)
  for ticket in tickets:
    unused[ticket] += 1

  # confirm every consecutive leg is a genuine, still-unused ticket.
  for step in range(len(route) - 1):
    leg: tuple[str, str] = (route[step], route[step + 1])
    if unused[leg] <= 0:
      return None
    unused[leg] -= 1

  return route

de_bruijn_sequence.pypython

from collections import defaultdict
from typing import Sequence

def de_bruijn_sequence(alphabet: Sequence[str], order: int) -> str:
  """
    A de Bruijn sequence B(alphabet, order): a cyclic string of length\n
    `len(alphabet) ** order` in which every length-`order` string over\n
    `alphabet` occurs exactly once as a contiguous (cyclic) window.\n
    `order` must be at least 1 and `alphabet` non-empty.\n
  """
  symbols: list[str] = list(alphabet)
  if order < 1:
    raise ValueError("order must be at least 1")
  if not symbols:
    raise ValueError("alphabet must be non-empty")

  if order == 1:
    # every single symbol is its own window; concatenation suffices.
    return "".join(symbols)

  # vertices are (order-1)-grams; an edge labelled by symbol `s` runs from a
  # gram to its suffix-plus-s. Each vertex has out-degree |alphabet|, so the
  # graph is balanced and an Eulerian circuit always exists.
  outgoing: dict[str, list[str]] = defaultdict(list)
  prefix_length: int = order - 1
  for gram in _all_grams(symbols, prefix_length):
    for symbol in symbols:
      outgoing[gram].append(symbol)

  start: str = symbols[0] * prefix_length
  edge_symbols: list[str] = _eulerian_edge_symbols(outgoing, start)

  # the circuit returns to `start`; reading one symbol per edge spells a
  # cyclic string of exactly |alphabet| ** order symbols.
  return "".join(edge_symbols)

def _all_grams(symbols: list[str], length: int) -> list[str]:
  """
    Every string of the given `length` over `symbols`, in lexicographic\n
    order relative to the symbols' own order.\n
  """
  grams: list[str] = [""]
  for _ in range(length):
    grams = [gram + symbol for gram in grams for symbol in symbols]
  return grams

def _eulerian_edge_symbols(
  outgoing: dict[str, list[str]],
  start: str,
) -> list[str]:
  """
    Hierholzer's circuit walk on the de Bruijn graph, returning one symbol\n
    per traversed edge. A vertex's successor along symbol `s` is its suffix\n
    followed by `s`, so the new symbol of each step is exactly the last\n
    character of the vertex stepped into.\n
  """
  next_edge: dict[str, int] = defaultdict(int)
  stack: list[str] = [start]
  circuit: list[str] = []
  while stack:
    current: str = stack[-1]
    choices: list[str] = outgoing[current]
    pointer: int = next_edge[current]
    if pointer < len(choices):
      symbol: str = choices[pointer]
      next_edge[current] = pointer + 1
      successor: str = (current[1:] + symbol) if current else symbol
      stack.append(successor)
    else:
      circuit.append(stack.pop())  # emit vertices in reverse on backtrack

  circuit.reverse()

  # circuit is v0, v1, ..., vE with v0 == vE (closed). The new symbol of edge
  # vi-1 -> vi is the last character of vi, so the sequence is the trailing
  # symbol of every vertex after the start — exactly E symbols.
  return [vertex[-1] for vertex in circuit[1:]]

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 $in-deg = out-deg$ everywhere; an Eulerian path iff one vertex has $out - in = + 1$ (start), one has $in - 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 $u se d$ 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, Ch. — Graph Traversal: Eulerian tours via the degree characterization, contrasted with the NP-complete Hamiltonian problem. ↩
Skiena, § — Eulerian Cycles: the even-degree (balanced) existence condition and its parity proof. ↩
CLRS, Ch. — Euler Tour (Problem): linear-time construction of an Eulerian tour on a graph satisfying the degree/balance conditions. ↩

When does an Eulerian tour exist?

Hierholzer's algorithm

Splice by splice on a concrete graph

The stack in action

Path versus circuit

Pitfalls

Applications

Takeaways

Footnotes