the Hamiltonian path problem
/ Hamiltonian -> ham-il-TOH-nee-an /
Imagine planning a sightseeing walk that visits every landmark in a city EXACTLY once, with no repeats and no skips, walking only along the streets that exist. A Hamiltonian path is exactly such a route through a graph: it touches every vertex once and only once. If the route also returns to its starting point, it is a Hamiltonian cycle. The question 'does such a route exist?' looks innocent but is one of the hardest in the toolkit.
Formally, given a graph G, a Hamiltonian path is a path that visits each vertex exactly once; a Hamiltonian cycle additionally closes back to the start. The decision problem asks whether G contains one. It is in NP: a certificate is an ordering of the vertices, and a verifier checks in polynomial time that the list is a permutation of all vertices and that each consecutive pair is joined by an edge. Beware a famous near-twin: the Eulerian path, which crosses every EDGE once, is easy (just check the degrees), but the Hamiltonian path, which visits every VERTEX once, is NP-complete. The surface similarity hides a chasm in difficulty.
Hamiltonicity is NP-complete, reached from 3-SAT through one of the most ingenious gadget reductions in the field, using variable-gadgets that can be traversed in two directions (encoding true/false) wired to clause-gadgets that force every clause to be satisfied. From the Hamiltonian cycle problem it is a short hop to the traveling-salesman decision problem: put weight 1 on existing edges and a large weight on the rest, and a tour of total weight n exists exactly when a Hamiltonian cycle does. This is why Hamiltonicity is a standard waypoint on the reduction map between graph problems and routing problems.
On vertices {A,B,C,D} with edges A-B, B-C, C-D, D-A, A-C, the ordering A, B, C, D is a Hamiltonian path: A-B, B-C, C-D all exist and each vertex appears once. Adding the edge D-A closes it into a Hamiltonian cycle A-B-C-D-A. The ordering is the certificate.
Hamiltonian path/cycle: visit every VERTEX exactly once. NP-complete, unlike the easy Eulerian path which uses every edge once.
Do not confuse it with the Eulerian path (every EDGE once), which is solvable in polynomial time by checking vertex degrees. Visiting every vertex once is the hard one.