the NP-completeness of Hamiltonian cycle
/ Hamiltonian = ham-il-TOH-nee-un /
A Hamiltonian cycle is a round trip through a network that visits EVERY city exactly once and returns home. It sounds like the friendlier Eulerian problem (cross every bridge once), which is easy — but visiting every VERTEX once, rather than every edge, turns out to be brutally hard. The Hamiltonian cycle problem asks: does a given graph contain such a tour at all? This is the combinatorial heart of the travelling salesman problem, and proving it NP-complete is a milestone in the zoo.
Membership in NP is immediate: a certificate is just the proposed order of vertices, v1, v2, ..., vn, v1, and a verifier checks in O(n) time that consecutive vertices are joined by edges and that all n vertices appear exactly once. The hard half is NP-hardness, shown by reducing a known NP-complete problem — classically 3-SAT or vertex cover — to Hamiltonian cycle using GADGETS. The idea: build a graph whose Hamiltonian cycles correspond exactly to solutions of the source problem. Each variable becomes a small 'two-way street' gadget that the cycle can traverse left-to-right or right-to-left, encoding true or false; each clause becomes a gadget that the cycle can thread through only if at least one of its literals was set to satisfy it. The pieces are wired so that a single Hamiltonian cycle threading the whole graph exists if and only if there is a consistent truth assignment satisfying every clause. Because every gadget is a fixed-size local widget and there are polynomially many, the construction runs in polynomial time, giving 3-SAT <=p Hamiltonian-cycle; with membership in NP, Hamiltonian cycle is NP-complete.
Why this one matters beyond its own statement: it is the gateway to the travelling salesman problem. Given a Hamiltonian-cycle instance, put weight 1 on existing edges and a huge weight on missing ones; then a tour of total weight n exists if and only if a Hamiltonian cycle exists — so Hamiltonian cycle <=p TSP-decision, making TSP NP-hard too. Two honest notes. First, mind the cousins: an EULERIAN circuit (every edge once) is checkable in polynomial time, while the look-alike Hamiltonian cycle (every vertex once) is NP-complete — a famous reminder that surface similarity says nothing about complexity. Second, NP-hardness is worst-case: real road networks and many structured graphs admit fast exact or near-optimal solutions in practice, so 'NP-complete' marks the worst instances, not a ban on ever solving the problem.
From Hamiltonian cycle to TSP: take any graph G on n vertices, and define a distance matrix with d(u,v) = 1 if uv is an edge of G and d(u,v) = 2 otherwise. Now ask the TSP question 'is there a tour of length <= n?'. Such a tour uses only weight-1 steps, i.e. only real edges, visiting each city once — exactly a Hamiltonian cycle of G. So solving this TSP instance answers the Hamiltonian-cycle question.
Hamiltonian cycle <=p TSP: weight 1 on edges, big weight on non-edges; a length-n tour = a Hamiltonian cycle.
Do not confuse with Eulerian circuits. Visiting every EDGE once (Eulerian) is in P, decidable by checking vertex degrees; visiting every VERTEX once (Hamiltonian) is NP-complete. Near-identical phrasing, opposite complexity — a vivid warning against judging hardness by appearance.