Graph Backtracking: m-Coloring & Hamiltonian Paths

The previous lesson cast N-Queens and Sudoku as constraint satisfaction problems and solved them with feasibility-pruned backtracking. Two of the most celebrated problems on graphs fit the same mold, and they are worth a lesson of their own because they are the canonical hard problems of the field: graph $m$ -coloring and the Hamiltonian path/cycle. Both have the same shape — a state we extend one vertex at a time, a candidate set, and a feasibility test that lets us abandon a doomed partial solution early — and both are NP-complete, so neither admits a known polynomial algorithm. They illustrate the central lesson of the module: exhaustive search is complete, pruning is sound, and although the worst case is exponential, a sharp prune collapses the explored tree on the instances we actually meet.

A recurring theme here is how close the boundary between easy and hard can be. We will see that asking for a tour that uses every edge once (an Eulerian tour) has a trivial degree condition, whereas asking for a walk that uses every vertex once (a Hamiltonian path) is NP-complete — a one-word change that crosses the tractability line.

Graph $m$ -coloring

Given an undirected graph $G = (V, E)$ and an integer $m$ , a proper $m$ -coloring assigns each vertex one of $m$ colors so that every edge joins two differently-colored vertices. The decision question is whether such a coloring exists; the optimization question — the smallest $m$ that works — defines the chromatic number $χ (G)$ .

This is a CSP in the precise sense of the last lesson: the variables are the vertices, each domain is the set ${1, \dots, m}$ of colors, and there is one constraint per edge, $color (u) \neq = color (v)$ . Backtracking colors the vertices in a fixed order $v_{0}, v_{1}, \dots, v_{n - 1}$ . At vertex $v_{i}$ the candidate colors are those not already used by an assigned neighbor; we try each, recurse, and backtrack when a vertex runs out of legal colors.

The feasibility test is local and cheap: a color $c$ is legal for $v_{i}$ exactly when no already-colored neighbor of $v_{i}$ has color $c$ , an $O (de g v_{i})$ scan.

Algorithm 1:

\textsc{Color}(i)

— color vertices in order, pruning monochromatic edges

1
if $i = n$ then
2
record the coloring; return true
all vertices colored
3
for $c \gets 1$ to $m$ do
4
if some neighbor of $v_i$ already has color $c$ then
5
continue
would break an edge — prune
6
$color[v_i] \gets c$
choose
7
if $\textsc{Color}(i+1)$ then return true
explore
8
$color[v_i] \gets 0$
un-choose (uncolor)
9
return false
no color worked — backtrack

The structure follows the choose/explore/un-choose template, with the constraint check inlined as the continue. When the loop falls through without a legal color, the vertex is uncolorable under the current partial assignment, so we return false and let the caller try a different color for $v_{i - 1}$ — the backtrack.

The pruning step is what makes this more than brute force. Rejecting color $c$ at $v_{i}$ discards every completion that would have colored $v_{i}$ with $c$ — a subtree of up to $m^{n - i - 1}$ leaves — at the cost of one neighbor scan. The figure shows the moment a partial coloring is forced to backtrack: a vertex whose neighbors already use all $m$ colors has an empty domain.

A partial

3

-coloring forced to backtrack: vertex

v

has three neighbors already colored

1

2

3

, so its domain

{1, 2, 3}

is empty and the search must undo an earlier choice

When $v$ 's three neighbors have already taken colors $1$ , $2$ , and $3$ , no color in ${1, 2, 3}$ is legal, so $Color$ returns false and control unwinds to recolor an ancestor. With $m = 4$ the same vertex would still have color $4$ available; this is precisely the search for the chromatic number — increase $m$ until the backtracking succeeds.

A proper

3

-coloring of a

5

-cycle with one chord: every edge joins two differently-tinted vertices, so no edge is monochromatic and the coloring is valid (green check). The three colors are shown as distinct blue tints.

Ordering and propagation

As in Sudoku, the algorithm is fixed but the vertex ordering controls how much of the tree we explore. Two cheap heuristics dominate in practice:¹

Highest-degree first. Color the most-constrained vertices early. A high-degree vertex has many neighbors competing for its color, so committing it first surfaces conflicts near the root, where a prune is most valuable. This is the degree-heuristic cousin of MRV.
Forward checking / propagation. When you color $v_{i}$ , strike that color from the candidate sets of its uncolored neighbors. If any neighbor's set empties, the branch is already dead — backtrack before descending into it.

These do not change the worst-case complexity, but they routinely turn an intractable search into an instant one on structured graphs.

Forward checking across three steps on a triangle. Step 1:

v_{0}

takes color

1

. Step 2:

v_{1}

takes

2

; both strike their color from

v_{2}

's domain. Step 3:

v_{2}

tries

1

but the edge to

v_{0}

is monochromatic (red conflict) so it must pick

3

. Colors shown as blue tints.

When is the problem easy?

A few special cases collapse to polynomial time and sharpen intuition for where the hardness lives:

The jump from $m = 2$ (a linear-time BFS) to $m = 3$ (NP-complete) shows how a small change in a problem statement can cross the tractability boundary — exactly the regime backtracking is built for.

A short trace shows the backtrack in action. Color the $5$ -cycle $v_{0} v_{1} v_{2} v_{3} v_{4}$ (edges between consecutive vertices, and $v_{4}$ – $v_{0}$ ) with $m = 3$ colors, taking the lowest legal color at each step and vertices in index order:

Step	Vertex	neighbors' colors	lowest legal	result
1	$v_{0}$	—	$1$	$v_{0} = 1$
2	$v_{1}$	${1}$	$2$	$v_{1} = 2$
3	$v_{2}$	${2}$	$1$	$v_{2} = 1$
4	$v_{3}$	${1}$	$2$	$v_{3} = 2$
5	$v_{4}$	${2, 1}$ (from $v_{3}$ and $v_{0}$ )	$3$	$v_{4} = 3$

The odd cycle forces the third color at $v_{4}$ : it borders both $v_{3} = 2$ and $v_{0} = 1$ , so colors $1$ and $2$ are illegal and only $3$ survives — which is why an odd cycle is not $2$ -colorable but is $3$ -colorable. Had $m$ been $2$ , step $5$ would have exhausted its domain, returned false, and forced a backtrack that, after trying every alternative, correctly reports no $2$ -coloring exists.

graph_coloring.pypython

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

from graph import Graph, Vertex

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

def _is_safe(
  vertex: Vertex[Label],
  color: int,
  coloring: dict[Label, int],
) -> bool:
  """
    Whether `color` is legal for `vertex` under the partial `coloring`:\n
    no already-colored neighbor wears the same color. An O(deg) scan.\n
  """
  for neighbor in vertex.neighbors():
    if coloring.get(neighbor.label) == color:
      return False
  return True

def color_graph(
  graph: Graph[Label],
  colors: int,
  order: Optional[list[Vertex[Label]]] = None,
) -> Optional[dict[Label, int]]:
  """
    A proper coloring of `graph` with at most `colors` colors, as a map from\n
    vertex label to a color in `1..colors`, or None if no such coloring\n
    exists. Vertices are colored in `order` (default: highest-degree first,\n
    the practical speedup that surfaces conflicts near the root).\n
  """
  if colors < 0:
    raise ValueError("number of colors must be non-negative")

  # fix the coloring order, then color vertices left-to-right.
  vertices: list[Vertex[Label]] = (
    order if order is not None else _highest_degree_first(graph)
  )
  coloring: dict[Label, int] = {}

  def extend(position: int) -> bool:
    if position == len(vertices):
      return True  # every vertex colored

    # try each color for this vertex: choose, recurse, un-choose on failure.
    current: Vertex[Label] = vertices[position]
    for candidate in range(1, colors + 1):
      if not _is_safe(current, candidate, coloring):
        continue  # would break an edge — prune
      coloring[current.label] = candidate
      if extend(position + 1):
        return True
      del coloring[current.label]

    return False  # no color worked — backtrack

  return coloring if extend(0) else None

def _highest_degree_first(graph: Graph[Label]) -> list[Vertex[Label]]:
  """
    Vertices sorted by descending degree — the most-constrained first.\n
    Committing a high-degree vertex early surfaces conflicts near the root,\n
    where a prune discards the largest subtree.\n
  """
  return sorted(
    graph.vertices,
    key=lambda vertex: len(vertex.outgoing),
    reverse=True,
  )

def is_colorable(graph: Graph[Label], colors: int) -> bool:
  """
    Whether `graph` admits a proper coloring with at most `colors` colors.\n
  """
  return color_graph(graph, colors) is not None

def chromatic_number(graph: Graph[Label]) -> int:
  """
    The least number of colors for a proper coloring of `graph`.\n
    Tests m = 1, 2, 3, ... until a coloring is found. An empty graph needs\n
    zero colors; a graph with edge-free vertices needs one.\n
  """
  vertex_count: int = len(graph)
  if vertex_count == 0:
    return 0

  # smallest m that works; n colors always suffice, so this terminates.
  for candidate in range(1, vertex_count + 1):
    if is_colorable(graph, candidate):
      return candidate

  return vertex_count  # unreachable — n colors always suffice

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)

Hamiltonian paths and cycles

A Hamiltonian path visits every vertex of $G$ exactly once; a Hamiltonian cycle is such a path that additionally returns to its start, so it closes into a single tour through all $n$ vertices. Deciding whether either exists is the textbook NP-complete problem.²

The backtracking framing mirrors permutation generation from the fundamentals lesson, with an adjacency constraint replacing free choice. The state is the path built so far; the candidate set at each step is the neighbors of the current endpoint that have not yet been visited; the feasibility test is simply is this neighbor unvisited and adjacent? We extend the path one vertex at a time, mark each chosen vertex visited (the make-move), recurse, and unmark on the way out (the undo-move).

Algorithm 2:

\textsc{Hamilton}(v, k)

— extend a path from

v

;

k

vertices placed

1
if $k = n$ then
2
return (start is adjacent to $v$ )
closes a cycle; drop test for a path
3
for each neighbor $u$ of $v$ do
4
if $visited[u]$ then continue
already on the path — prune
5
$visited[u] \gets \text{true}$ ; append $u$ to path
choose
6
if $\textsc{Hamilton}(u, k+1)$ then return true
explore
7
$visited[u] \gets \text{false}$ ; pop $u$ from path
un-choose
8
return false
every extension failed — backtrack

Started from a fixed vertex with that vertex marked visited and $k = 1$ , this finds a Hamiltonian cycle; deleting the final adjacency test finds a Hamiltonian path. Trying every starting vertex (or fixing one, since a cycle can begin anywhere) covers all tours.

The search tree is a tree of partial paths. Its branches die for two reasons, and good pruning catches both early:

Visited neighbor. A neighbor already on the path cannot be revisited — the continue above.
Dead end. The current endpoint has no unvisited neighbor yet $k < n$ ; the loop falls through, returns false, and we backtrack to try a different earlier choice.

Hamiltonian-path search tree from

a

on a

5

-vertex graph: the path

a, b, c

dead-ends (its only neighbors are visited), pruning that whole subtree (red, dashed); the accented path

a, b, e, d, c

visits all five

The accented branch threads all five vertices: $a, b, e, d, c$ . The branch through $a, b, c$ stalls because $c$ 's only neighbors are already on the path, so the subtree below it is pruned without ever materializing the remaining permutations — a single feasibility check prunes an exponential number of dead extensions.

hamiltonian_path.pypython

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

from graph import Graph, Vertex

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

def _reachable_count(
  start: Vertex[Label],
  visited: set[Label],
) -> int:
  """
    How many still-unvisited vertices are reachable from `start` using only\n
    unvisited vertices. The current endpoint passes itself as `start`; if the\n
    count falls short of the unvisited total, some vertex has been stranded\n
    and no completion exists — the disconnection prune.\n
  """
  # flood-fill from the endpoint over unvisited vertices only.
  seen: set[Label] = {start.label}
  stack: list[Vertex[Label]] = [start]

  while stack:
    current: Vertex[Label] = stack.pop()
    for neighbor in current.neighbors():
      if neighbor.label in visited or neighbor.label in seen:
        continue
      seen.add(neighbor.label)
      stack.append(neighbor)

  return len(seen)

def _search(
  current: Vertex[Label],
  start: Vertex[Label],
  visited: set[Label],
  path: list[Label],
  total: int,
  require_cycle: bool,
) -> bool:
  """
    Extend the path from `current`; `len(path)` vertices are already placed.\n
    Returns True once a full Hamiltonian path (or cycle) is recorded in\n
    `path`, leaving it intact for the caller.\n
  """
  # all vertices placed: a cycle also needs an edge back to the start.
  if len(path) == total:
    if require_cycle:
      return start.label in {edge.target.label for edge in current.outgoing}
    return True

  # disconnection prune: every unvisited vertex must still be reachable
  # from the current endpoint through unvisited vertices.
  if _reachable_count(current, visited) != total - len(path) + 1:
    return False

  # try each unvisited neighbor: choose, recurse, un-choose on failure.
  for neighbor in current.neighbors():
    if neighbor.label in visited:
      continue  # already on the path — prune
    visited.add(neighbor.label)
    path.append(neighbor.label)
    if _search(neighbor, start, visited, path, total, require_cycle):
      return True
    visited.discard(neighbor.label)
    path.pop()

  return False  # every extension failed — backtrack

def hamiltonian_path(
  graph: Graph[Label],
  source: Optional[Label] = None,
) -> Optional[list[Label]]:
  """
    A Hamiltonian path of `graph` as the ordered list of vertex labels, or\n
    None if none exists. With `source` given, the path must start there;\n
    otherwise every starting vertex is tried.\n
  """
  return _find(graph, source, require_cycle=False)

def hamiltonian_cycle(
  graph: Graph[Label],
  source: Optional[Label] = None,
) -> Optional[list[Label]]:
  """
    A Hamiltonian cycle of `graph` as the ordered list of vertex labels\n
    (the start is listed once; the closing edge back to it is implied), or\n
    None if none exists. A cycle may begin anywhere, so one starting vertex\n
    suffices when `source` is left unset.\n
  """
  return _find(graph, source, require_cycle=True)

def _find(
  graph: Graph[Label],
  source: Optional[Label],
  require_cycle: bool,
) -> Optional[list[Label]]:
  """
    Shared driver for the path and cycle searches.\n
  """
  total: int = len(graph)
  if total == 0:
    return [] if not require_cycle else None
  if require_cycle and total < 3:
    return None  # a cycle needs at least three distinct vertices

  # degree-1 prune: a vertex of degree 1 can never sit inside a cycle.
  if require_cycle and any(
    len(vertex.outgoing) < 2 for vertex in graph.vertices
  ):
    return None

  starts: list[Vertex[Label]]
  if source is not None:
    starts = [graph.vertex(source)]
  elif require_cycle:
    starts = [graph.vertices[0]]  # a cycle can begin anywhere
  else:
    starts = graph.vertices

  for start in starts:
    visited: set[Label] = {start.label}
    path: list[Label] = [start.label]
    if _search(start, start, visited, path, total, require_cycle):
      return path
  return 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)

Pruning that pays

Beyond the two basic cuts, two classical prunes shrink the tree sharply on sparse graphs:³

Each prune is a sound test: it cuts only branches that provably hold no Hamiltonian path. So the search stays complete — if a tour exists, some surviving branch finds it.

The Eulerian contrast

Compare Hamiltonian with its near-twin. An Eulerian tour uses every edge exactly once; a Hamiltonian cycle uses every vertex exactly once. The two sound symmetric, but their difficulty differs sharply.

There is no remotely comparable characterization for Hamiltonicity. No simple local condition decides whether a Hamiltonian path exists; the problem is NP-complete, and the backtracking search above is essentially the best general approach known.

Same near-symmetric questions, opposite difficulty: Eulerian (every edge once) is decided in

O (V + E)

by a degree parity test; Hamiltonian (every vertex once) is NP-complete and needs backtracking

That a one-word swap — edge for vertex — moves a problem from a linear-time parity test to NP-completeness shows how fragile tractability is, and why a general-purpose, prune-driven search matters.

eulerian_condition.pypython

from collections.abc import Hashable
from typing import TypeVar

from graph import Graph, Vertex

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

def _degree(vertex: Vertex[Label]) -> int:
  """
    The degree of `vertex` in an undirected graph: its outgoing-edge count,\n
    since an undirected Graph stores each edge once in each direction.\n
  """
  return len(vertex.outgoing)

def _vertices_with_edges(graph: Graph[Label]) -> list[Vertex[Label]]:
  """
    The vertices that carry at least one edge — isolated vertices do not\n
    affect Eulerian feasibility and are ignored by the connectivity test.\n
  """
  return [vertex for vertex in graph.vertices if vertex.outgoing]

def _edges_connected(graph: Graph[Label]) -> bool:
  """
    Whether all edges lie in a single connected component, i.e. every\n
    non-isolated vertex is reachable from one of them.\n
  """
  active: list[Vertex[Label]] = _vertices_with_edges(graph)
  if not active:
    return True  # no edges at all — vacuously connected

  # flood-fill from any edge-bearing vertex over all reachable vertices.
  start: Vertex[Label] = active[0]
  seen: set[Label] = {start.label}
  stack: list[Vertex[Label]] = [start]

  while stack:
    current: Vertex[Label] = stack.pop()
    for neighbor in current.neighbors():
      if neighbor.label not in seen:
        seen.add(neighbor.label)
        stack.append(neighbor)

  # connected iff the fill reached every edge-bearing vertex.
  return len(seen) == len(active)

def odd_degree_count(graph: Graph[Label]) -> int:
  """
    How many vertices have odd degree — the quantity Euler's condition\n
    turns on.\n
  """
  return sum(1 for vertex in graph.vertices if _degree(vertex) % 2 == 1)

def has_eulerian_circuit(graph: Graph[Label]) -> bool:
  """
    Whether `graph` has an Eulerian circuit (a closed tour using every edge\n
    exactly once): its edges are connected and every vertex has even degree.\n
  """
  return _edges_connected(graph) and odd_degree_count(graph) == 0

def has_eulerian_path(graph: Graph[Label]) -> bool:
  """
    Whether `graph` has an Eulerian path (an open or closed walk using every\n
    edge exactly once): its edges are connected and at most two vertices\n
    have odd degree.\n
  """
  return _edges_connected(graph) and odd_degree_count(graph) in (0, 2)

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)

Correctness and cost

Both searches inherit their correctness from the backtracking skeleton, and the argument is the same two-part claim every lesson in this module uses.

The cost is the familiar exponential. The running time is the size of the explored tree times the per-node work, and the tree is exponential in the worst case because both problems are NP-complete and no polynomial bound is possible unless $P = NP$ .

What pruning buys is the gap between worst case and typical case. On a graph with few legal colorings, the neighbor-conflict check empties most branches near the root; on a sparse graph, the dead-end and disconnection prunes sever the path tree long before depth $n$ . The explored tree shrinks to a sliver of $m^{n}$ or $n!$ , and the search finishes in milliseconds on instances far larger than the worst-case bound would suggest — the exponential-but-fast distinction made precise. For genuinely hard instances where no prune bites, the coping strategies of the intractability module — approximation, heuristics, restriction to tractable subclasses — take over.

Coloring in the wild and the Hamiltonicity frontier

Both problems in this lesson are NP-complete, yet both are solved at scale every day — through smarter search and problem-specific structure.

DSATUR and register allocation. For coloring, the standard practical choice is Brélaz's DSATUR heuristic (1979): color the vertex with the highest saturation — the most distinctly-colored neighbors — breaking ties by degree, which is MRV specialized to coloring.⁴ Its most consequential application is register allocation in compilers: Chaitin (1982) modeled assigning program variables to a fixed set of CPU registers as graph coloring, where vertices are live variables, edges join variables live at the same time, and colors are registers; a $k$ -coloring is a valid allocation into $k$ registers, and uncolorable vertices are spilled to memory.⁵ Every optimizing compiler runs a coloring-based allocator descended from this idea.

The Four-Color Theorem. The bound that any planar graph needs at most $4$ colors is one of mathematics' most famous results — and the first major theorem proved with essential help from a computer. Appel and Haken (1976) reduced it to $1, 936$ unavoidable configurations checked by machine; Robertson, Sanders, Seymour, and Thomas (1997) gave a cleaner, fully verified proof with $633$ configurations.⁶ It caps the coloring difficulty for the planar graphs that maps and many circuits induce.

Tractable cases of Hamiltonicity. Although Hamiltonicity is NP-complete in general, whole families are easy. Dirac's theorem (1952) guarantees a Hamiltonian cycle whenever every vertex has degree $\geq n /2$ ; Ore's theorem (1960) relaxes this to non-adjacent pairs summing to $\geq n$ .⁷ These are sufficient conditions — dense graphs are automatically Hamiltonian — mirroring the Eulerian degree condition in spirit, even though no necessary and sufficient local test can exist unless $P = NP$ . And the Held–Karp dynamic program (1962) solves Hamiltonicity and the TSP exactly in $O (2^{n} n^{2})$ time — exponential, but a vast improvement over the $n!$ of naive backtracking.⁸

The tractability map of this lesson. Easy (green):

2

-coloring, planar

4

-coloring, Eulerian tours, dense-graph Hamiltonicity (Dirac/Ore). Hard (blue): general

3

-coloring and general Hamiltonicity — NP-complete, met by pruned backtracking.

Takeaways

Graph $m$ -coloring is a CSP: vertices are variables, colors are domains, and each edge contributes one inequality constraint. Backtracking colors vertices in order and rejects a color the instant an assigned neighbor already has it, pruning a subtree of up to $m^{n - i - 1}$ leaves per cut.
The chromatic number $χ (G)$ is the least feasible $m$ ; $2$ -coloring is a linear-time bipartiteness test, but $3$ -coloring is NP-complete — a sharp tractability jump. Highest-degree-first ordering and forward checking are the practical speedups.
A Hamiltonian path visits every vertex once (a cycle also returns to the start). Backtracking extends a path along unvisited adjacent neighbors, marking and unmarking each vertex, and backtracks at dead ends; degree-1 and disconnection prunes shrink the tree on sparse graphs.
The Eulerian contrast: every-edge-once is decided in $O (V + E)$ by a degree-parity test (Euler), while every-vertex-once is NP-complete — a one-word change across the tractability line.
Both searches are complete (exhaustive DFS) with sound prunes (only doomed subtrees cut), so no solution is lost. The worst case is exponential ( $m^{n}$ colorings, $n!$ orderings), but pruning collapses the explored tree on real instances, with the intractability module's coping strategies as the fallback for the hard ones.

Skiena, § — Combinatorial Search: graph coloring by backtracking, the chromatic number, and vertex ordering / propagation as the practical speedups. ↩
CLRS, Ch. 34 — NP-Completeness: the Hamiltonian-cycle problem and the proof that deciding Hamiltonicity is NP-complete. ↩
Skiena, § — Combinatorial Search: finding Hamiltonian cycles by backtracking with connectivity and degree-based pruning. ↩
Brélaz, D. (1979), New methods to color the vertices of a graph, Communications of the ACM 22(4), 251–256 — the DSATUR saturation-degree heuristic for graph coloring. ↩
Chaitin, G. J. (1982), Register allocation & spilling via graph coloring, Proc. SIGPLAN '82 Symposium on Compiler Construction, 98–105 — modeling register allocation as graph coloring with spilling for uncolorable vertices. ↩
Appel, K. & Haken, W. (1977), Every planar map is four colorable, Illinois Journal of Mathematics 21(3), 429–567; and Robertson, N., Sanders, D., Seymour, P. & Thomas, R. (1997), The four-colour theorem, Journal of Combinatorial Theory, Series B 70(1), 2–44 — the computer-assisted proof and its streamlined verification. ↩
Dirac, G. A. (1952), Some theorems on abstract graphs, Proc. London Mathematical Society 3(1), 69–81; and Ore, O. (1960), Note on Hamilton circuits, American Mathematical Monthly 67(1), 55 — sufficient minimum-degree conditions for Hamiltonicity. ↩
Held, M. & Karp, R. M. (1962), A dynamic programming approach to sequencing problems, Journal of the SIAM 10(1), 196–210 — the $O (2^{n} n^{2})$ exact algorithm for the Hamiltonian-path/TSP problem. ↩

Graph m-coloring

Ordering and propagation

When is the problem easy?

Hamiltonian paths and cycles

Pruning that pays

The Eulerian contrast

Correctness and cost

Coloring in the wild and the Hamiltonicity frontier

Takeaways

Footnotes

Graph $m$ -coloring