Chapter IX Directed Hamilton Circuit

Visit every node, exactly once

It sounds like Euler's bridges, but Euler used every edge once. Hamilton uses every vertex once — and that small change makes it NP-complete.

A Hamilton circuit on a directed graph is a cycle passing through every vertex exactly once:

v_{1} \to v_{2} \to \dots \to v_{n} \to v_{1}, {v_{1}, \dots, v_{n}} = V, (v_{i}, v_{i + 1}) \in E . (1)

The decision problem (does a sequence (1) exist?) is NP-complete; Karp reduced 3-SAT to it.

Compare this with the Eulerian circuit problem — visit every edge once — which is solved in linear time by Hierholzer's algorithm under a simple local condition:

indeg (v) = outdeg (v) for every v \in V . (2)

There is no analogous characterization for (1) — the obstruction is fundamentally global. Special graph classes (tournaments, bipartite, cubic) have polynomial cases; the general problem doesn't.

Figures, in plain terms

(1)

Read left to right: v₁ → v₂ → ... → v_n → v₁ spells out a sequence of vertices, with arrows showing the direction of traversal. The last arrow loops back from v_n to v₁, closing the path into a cycle.

{v₁, ..., v_n} = V demands the visited vertices are exactly the whole vertex set. Listed in braces, no duplicates allowed by definition of a set, so each vertex appears once.

(v_i, v_{i+1}) ∈ E says every consecutive pair in the sequence is an actual edge of the graph. The subscript i ranges over the steps; v_{i+1} is the next vertex.

Reassembled: a Hamilton circuit is an ordering of all vertices into a closed walk where every step uses a real edge.

(2)

indeg(v) counts the edges pointing into v; outdeg(v) counts the edges pointing out.

The condition demands these match for every vertex. The for every v ∈ V clause uses the in-set symbol introduced before — quantifies over all vertices.

This is the local check that makes the Eulerian problem easy: count incoming and outgoing edges at each vertex. Every Eulerian circuit needs this balance, and the converse (with weak connectivity) also holds.

By contrast, no analogous local condition exists for Hamilton circuits — the obstruction lives in the whole graph at once.