---
title: "Graph Backtracking: m-Coloring & Hamiltonian Paths"
module: Backtracking & Search
moduleNumber: 9
lessonNumber: 4
order: 904
summary: |
  Two famous graph problems have no known efficient algorithm, yet yield cleanly
  to backtracking with the right pruning. **Graph $m$-coloring** assigns one of
  $m$ colors to each vertex so no edge is monochromatic; we color vertices in turn
  and reject a color the instant a neighbor already has it. **Hamiltonian
  path/cycle** asks for a walk visiting every vertex exactly once; we extend a path
  greedily and backtrack on dead ends. Both are NP-complete, so the worst case is
  exponential — but feasibility pruning and good vertex ordering make real
  instances tractable, and the contrast with the easy Eulerian condition shows why.
topics: [Backtracking]
sources:
  - book: Skiena
    ref: "§ — Combinatorial Search (graph coloring, Hamiltonian cycles)"
  - book: Erickson
    ref: "Ch. — Backtracking"
  - book: CLRS
    ref: "Ch. 34 — NP-Completeness (Hamiltonian cycle, graph coloring)"
practice:
  - title: 'Flower Planting With No Adjacent'
    slug: flower-planting-with-no-adjacent
    difficulty: Medium
  - title: 'Possible Bipartition'
    slug: possible-bipartition
    difficulty: Medium
  - title: 'Reconstruct Itinerary'
    slug: reconstruct-itinerary
    difficulty: Hard
  - title: 'Find the Shortest Superstring'
    slug: find-the-shortest-superstring
    difficulty: Hard
---

The previous lesson cast [N-Queens and Sudoku](/algorithms/backtracking/constraint-search)
as constraint satisfaction problems and solved them with feasibility-pruned
backtracking. Two of the most celebrated problems on [graphs](/algorithms/graphs/representations-and-traversal)
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](/algorithms/intractability/np-completeness),
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** $\chi(G)$.

> **Definition (Chromatic number).** The chromatic number $\chi(G)$ is the least
> $m$ for which $G$ has a proper $m$-coloring. A graph is **$m$-colorable** iff
> $\chi(G) \le m$, and we can compute $\chi(G)$ by testing $m = 1, 2, 3, \dots$
> until a coloring is found.

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**, $\text{color}(u) \ne \text{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(\deg v_i)$ scan.

```algorithm
caption: $\textsc{Color}(i)$ — color vertices in order, pruning monochromatic edges
number: 1
if $i = n$ then
  record the coloring; return true // all vertices colored
for $c \gets 1$ to $m$ do
  if some neighbor of $v_i$ already has color $c$ then
    continue // would break an edge — prune
  $color[v_i] \gets c$ // choose
  if $\textsc{Color}(i+1)$ then return true // explore
  $color[v_i] \gets 0$ // un-choose (uncolor)
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.

$$
% caption: 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
\begin{tikzpicture}[
  >=stealth, font=\small,
  vtx/.style={draw, circle, minimum size=9mm, inner sep=1pt, font=\small},
  dead/.style={draw=red!75!black, very thick, circle, minimum size=9mm, inner sep=1pt, text=red!75!black, font=\small},
  lbl/.style={draw=none, font=\scriptsize},
  every edge/.style={draw, black}]
  \definecolor{acc}{HTML}{2348F2}
  % three already-colored neighbors: the assigned colors 1,2,3 shown as distinct blue tints
  \node[vtx, fill=acc!10, draw=acc] (a) at (-1.7,1.2) {$1$};
  \node[vtx, fill=acc!22, draw=acc] (b) at (-2.2,-0.6) {$2$};
  \node[vtx, fill=acc!36, draw=acc] (c) at (-0.3,-1.7) {$3$};
  % the vertex with no legal color
  \node[dead] (v) at (0.2,-0.1) {$v$};
  \draw (v) edge (a) (v) edge (b) (v) edge (c);
  % its empty domain
  \node[lbl, text=acc, align=left] at (3.0,0.7) {\texttt{neighbors use all three colors}};
  \node[lbl, text=red!75!black, align=left] at (2.75,-0.05) {\texttt{domain of v is empty}};
  \node[lbl, text=red!75!black, align=left] at (2.7,-0.8) {\texttt{no legal color remains}};
  \node[lbl, text=red!75!black, align=center] at (1.8,-2.4) {\texttt{must backtrack}};
\end{tikzpicture}
$$

When $v$'s three neighbors have already taken colors $1$, $2$, and $3$, no color
in $\{1,2,3\}$ is legal, so $\textsc{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.

$$
% caption: 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.
\begin{tikzpicture}[
  >=stealth, font=\small,
  vtx/.style={draw, circle, minimum size=9mm, inner sep=1pt, font=\small, draw=acc},
  every edge/.style={draw, black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \useasboundingbox (-2.6,2.6) rectangle (5.4,-2.8);
  % a 5-cycle with vertices colored 1,2,3,1,2 (proper)
  \node[vtx, fill=acc!10]  (p1) at (0,2.2)    {$1$};
  \node[vtx, fill=acc!24]  (p2) at (2.1,0.7)  {$2$};
  \node[vtx, fill=acc!38]  (p3) at (1.3,-1.8) {$3$};
  \node[vtx, fill=acc!10]  (p4) at (-1.3,-1.8){$1$};
  \node[vtx, fill=acc!38]  (p5) at (-2.1,0.7) {$3$};
  \draw (p1) edge (p2) (p2) edge (p3) (p3) edge (p4) (p4) edge (p5) (p5) edge (p1);
  \draw (p2) edge (p5);
  \node[font=\footnotesize, text=green!50!black, align=left] at (4.0,0.6) {\texttt{every edge has}};
  \node[font=\footnotesize, text=green!50!black, align=left] at (4.0,0.0) {\texttt{two colors}};
  \node[font=\footnotesize, text=green!50!black, align=left] at (4.0,-0.6) {\texttt{valid coloring}};
\end{tikzpicture}
$$

### 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:[^skiena-color]

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

$$
% caption: 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.
\begin{tikzpicture}[
  >=stealth, font=\small,
  vtx/.style={draw=acc, circle, minimum size=7mm, inner sep=1pt, font=\footnotesize},
  open/.style={draw=black, circle, minimum size=7mm, inner sep=1pt, font=\footnotesize},
  lbl/.style={draw=none, font=\scriptsize, align=center},
  every edge/.style={draw, black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % --- step 1 ---
  \begin{scope}
    \node[vtx, fill=acc!12] (a0) at (0,1.3) {$1$};
    \node[open] (b0) at (-0.9,-0.4) {$?$};
    \node[open] (c0) at (0.9,-0.4) {$?$};
    \draw (a0) edge (b0) (a0) edge (c0) (b0) edge (c0);
    \node[lbl] at (0,-1.5) {assign $v_0$};
  \end{scope}
  % --- step 2 ---
  \begin{scope}[xshift=42mm]
    \node[vtx, fill=acc!12] (a1) at (0,1.3) {$1$};
    \node[vtx, fill=acc!28] (b1) at (-0.9,-0.4) {$2$};
    \node[open] (c1) at (0.9,-0.4) {$?$};
    \draw (a1) edge (b1) (a1) edge (c1) (b1) edge (c1);
    \node[lbl] at (0,-1.5) {assign $v_1$};
  \end{scope}
  % --- step 3 ---
  \begin{scope}[xshift=84mm]
    \node[vtx, fill=acc!12] (a2) at (0,1.3) {$1$};
    \node[vtx, fill=acc!28] (b2) at (-0.9,-0.4) {$2$};
    \node[draw=red!75!black, very thick, circle, minimum size=7mm, inner sep=1pt, font=\footnotesize, text=red!75!black] (c2) at (0.9,-0.4) {$1$};
    \draw[red!75!black, very thick] (a2) edge (c2);
    \draw (a2) edge (b2) (b2) edge (c2);
    \node[lbl, text=red!75!black] at (0,-1.5) {clash then retry};
  \end{scope}
\end{tikzpicture}
$$

### When is the problem easy?

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

> **Remark (Easy and hard colorings).**
> - **$m = 2$** is just a [bipartiteness](/algorithms/graphs/bipartite-matching)
>   test: a graph is $2$-colorable iff it has no odd cycle, decidable by a single
>   BFS/DFS that two-colors components in $O(V + E)$.
> - **Trees** need only $2$ colors; any planar graph needs at most $4$ (the
>   Four-Color Theorem).
> - **$m \ge 3$** in general is **NP-complete**: deciding $3$-colorability of an
>   arbitrary graph is one of Karp's original hard problems, so no efficient exact
>   algorithm is known.

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.

::impl{algo="graph_coloring"}

## 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.[^clrs-hc]

> **Definition (Hamiltonian path/cycle).** A **Hamiltonian path** is a permutation
> $v_{\pi(0)}, v_{\pi(1)}, \dots, v_{\pi(n-1)}$ of all $n$ vertices such that each
> consecutive pair is joined by an edge. It is a **Hamiltonian cycle** if, in
> addition, the last vertex is adjacent to the first.

The backtracking framing mirrors permutation generation from the
[fundamentals lesson](/algorithms/backtracking/backtracking-fundamentals), 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
caption: $\textsc{Hamilton}(v, k)$ — extend a path from $v$; $k$ vertices placed
number: 2
if $k = n$ then
  return (start is adjacent to $v$) // closes a cycle; drop test for a path
for each neighbor $u$ of $v$ do
  if $visited[u]$ then continue // already on the path — prune
  $visited[u] \gets \text{true}$; append $u$ to path // choose
  if $\textsc{Hamilton}(u, k+1)$ then return true // explore
  $visited[u] \gets \text{false}$; pop $u$ from path // un-choose
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.

$$
% caption: 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
\begin{tikzpicture}[
  >=stealth, font=\small,
  level distance=13mm,
  level 1/.style={sibling distance=54mm},
  level 2/.style={sibling distance=30mm},
  level 3/.style={sibling distance=16mm},
  nd/.style={draw, circle, minimum size=8mm, inner sep=1pt, font=\small},
  good/.style={draw=acc, very thick, circle, minimum size=8mm, inner sep=1pt, text=acc, font=\small},
  dead/.style={draw=red!75!black, dashed, circle, minimum size=8mm, inner sep=1pt, text=red!75!black, font=\small},
  lbl/.style={draw=none, font=\scriptsize},
  edge from parent/.style={draw, ->, black}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-6.0,0.8) rectangle (6.8,-7.6);
  \node[good] {$a$}
    child {node[good] {$b$}
      child {node {$c$}
        child {node[dead] {dead} edge from parent[draw=red!75!black, dashed]}
        edge from parent}
      child {node[good] {$e$}
        child {node[good] {$d$}
          child {node[good] {$c$} edge from parent[draw=acc, ->, very thick]}
          edge from parent[draw=acc, ->, very thick]}
        edge from parent[draw=acc, ->, very thick]}
      edge from parent[draw=acc, ->, very thick]}
    child {node {$e$}
      child {node {$d$}
        child {node {$c$}
          child {node[dead] {dead} edge from parent[draw=red!75!black, dashed]}
          edge from parent}
        edge from parent}
      edge from parent};
  % annotations
  \node[lbl, text=red!75!black, align=center] at (-3.5,-5.0) {\texttt{path a-b-c stalls}};
  \node[lbl, text=red!75!black, align=center] at (-3.5,-5.6) {\texttt{all neighbors used}};
  \node[lbl, acc, align=center] at (4.6,-5.0) {\texttt{a-b-e-d-c}};
  \node[lbl, acc, align=center] at (4.6,-5.6) {\texttt{visits all 5 vertices}};
\end{tikzpicture}
$$

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.

::impl{algo="hamiltonian_path"}

### Pruning that pays

Beyond the two basic cuts, two classical prunes shrink the tree sharply on sparse
graphs:[^skiena-hc]

> **Remark (Connectivity and degree prunes).**
> - **Degree-1 endpoints.** A vertex of degree $1$ can only be an _endpoint_ of a
>   Hamiltonian path, and any vertex of degree $1$ makes a Hamiltonian _cycle_
>   impossible outright — the search can stop immediately.
> - **Disconnection prune.** After choosing the next vertex, if the unvisited
>   vertices (plus the current endpoint) no longer form a connected subgraph that
>   the path can still reach, no completion exists — backtrack now. A vertex that
>   has become unreachable can never be added later.

Each prune is a [sound](/algorithms/foundations/what-is-an-algorithm) test: it cuts
only branches that provably hold no Hamiltonian path. So the search stays
[complete](/algorithms/foundations/what-is-an-algorithm) — if a tour exists, some
surviving branch finds it.

### The Eulerian contrast

Compare Hamiltonian with its near-twin. An [**Eulerian
tour**](/algorithms/graphs/eulerian-tours) uses every _edge_ exactly once; a
Hamiltonian cycle uses every _vertex_ exactly once. The two sound symmetric, but
their difficulty differs sharply.

> **Theorem (Euler's condition).** A connected (multi)graph has an Eulerian
> **circuit** iff every vertex has even degree, and an Eulerian **path** iff at
> most two vertices have odd degree. The condition is checkable in $O(V + E)$, and
> Hierholzer's algorithm _constructs_ the tour in linear time.

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.

$$
% caption: 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
\begin{tikzpicture}[
  >=stealth, font=\small,
  box/.style={draw, minimum width=42mm, minimum height=20mm, align=center, inner sep=4pt},
  tag/.style={draw=none, font=\footnotesize, align=center},
  lbl/.style={draw=none, font=\scriptsize, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \useasboundingbox (-0.4,1.7) rectangle (10.4,-3.2);
  % Eulerian — easy
  \node[tag, green] at (2.4,1.35) {\texttt{Eulerian: every edge once}};
  \node[box, draw=green, fill=green!8] (e) at (2.4,0) {\texttt{parity of degrees}\\ \texttt{decides it}};
  \node[lbl, green] at (2.4,-1.55) {\texttt{O(V+E) check}};
  \node[lbl, green] at (2.4,-2.25) {\texttt{Hierholzer builds it}};
  % Hamiltonian — hard
  \node[tag, acc] at (7.6,1.35) {\texttt{Hamiltonian: every vertex once}};
  \node[box, draw=acc, fill=acc!8] (h) at (7.6,0) {\texttt{no local condition}\\ \texttt{known}};
  \node[lbl, acc] at (7.6,-1.55) {\texttt{NP-complete}};
  \node[lbl, acc] at (7.6,-2.25) {\texttt{backtracking search}};
\end{tikzpicture}
$$

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.

::impl{algo="eulerian_condition"}

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

> **Claim (completeness).** $\textsc{Color}$ and $\textsc{Hamilton}$ each report a
> solution whenever one exists.

> **Proof.** Each procedure is an exhaustive [depth-first
> search](/algorithms/foundations/what-is-an-algorithm) of the full state-space
> tree: $\textsc{Color}$ tries _every_ color for $v_i$ that the constraints permit
> before returning `false`, and $\textsc{Hamilton}$ tries _every_ unvisited
> adjacent extension before giving up. The only branches not explored are those a
> constraint has already ruled out — a color used by a neighbor, a vertex already
> on the path — and such a branch can contain no valid solution. Pruning is
> therefore **sound**: it removes only doomed subtrees. A sound prune over an
> exhaustive search leaves the search **complete**, so if a proper coloring (resp.
> Hamiltonian path) exists, the corresponding root-to-leaf path is never cut and is
> eventually reached. $\qed$

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 $\mathrm{P} = \mathrm{NP}$.

> **Theorem (worst-case cost).** Unpruned, $\textsc{Color}$ explores up to $m^n$
> colorings and $\textsc{Hamilton}$ up to $n!$ vertex orderings. Pruning removes
> dominated subtrees but does not lower the worst-case exponential order.

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](/algorithms/backtracking/backtracking-fundamentals)
distinction made precise. For genuinely hard instances where no prune bites, the
[coping strategies](/algorithms/intractability/coping-with-hardness) 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.[^dsatur] 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.[^chaitin] 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.[^4ct] 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 $\ge n/2$; **Ore's theorem**
(1960) relaxes this to non-adjacent pairs summing to $\ge n$.[^dirac] 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 $\mathrm{P} = \mathrm{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.[^heldkarp]

$$
% caption: 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.
\begin{tikzpicture}[font=\small, >=stealth,
  easy/.style={draw=grn, fill=grn!8, minimum height=7mm, inner sep=3pt, font=\footnotesize},
  hard/.style={draw=acc, fill=acc!8, minimum height=7mm, inner sep=3pt, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  \node[grn, font=\footnotesize] at (2.1,2.5) {polynomial};
  \node[easy] at (2.1,1.8) {$2$-coloring (bipartite test)};
  \node[easy] at (2.1,1.0) {planar $4$-coloring};
  \node[easy] at (2.1,0.2) {Eulerian tour (parity)};
  \node[easy] at (2.1,-0.6) {dense Hamiltonicity (Dirac/Ore)};
  \node[acc, font=\footnotesize] at (7.7,2.5) {NP-complete};
  \node[hard] at (7.7,1.8) {general $3$-coloring};
  \node[hard] at (7.7,1.0) {general Hamiltonicity};
  \node[hard] at (7.7,0.2) {exact TSP};
  \node[font=\footnotesize, black, align=center] at (7.7,-0.7) {met by pruned\\ backtracking};
\end{tikzpicture}
$$

## 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** $\chi(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-color]: **Skiena**, § — Combinatorial Search: graph coloring by backtracking, the chromatic number, and vertex ordering / propagation as the practical speedups.
[^clrs-hc]: **CLRS**, Ch. 34 — NP-Completeness: the Hamiltonian-cycle problem and the proof that deciding Hamiltonicity is NP-complete.
[^skiena-hc]: **Skiena**, § — Combinatorial Search: finding Hamiltonian cycles by backtracking with connectivity and degree-based pruning.
[^dsatur]: **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]: **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.
[^4ct]: **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]: **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.
[^heldkarp]: **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.