Chapter 5
Euler Tours and Hamilton Cycles
Traverse every *edge* and the problem is linear; traverse every *vertex* and it is NP-complete. The border between those two is the most instructive line in the subject.
6 pages4,472 words11 problems0 interactive
1Euler Tours: When They ExistEuler's degree condition, why it is both necessary and sufficient, and the directed/undirected split.2Hierholzer's Linear AlgorithmBuild an Euler tour in O(n + m) with a stack, a pointer per vertex, and one ordering subtlety.3De Bruijn SequencesThe shortest string containing every k-mer: an Eulerian cycle on (k−1)-bit states.4When Hamiltonian Cycles Must ExistDirac, Ore and Pósa — sufficient degree conditions, and the rotation-extend argument behind them.5Held–Karp: Hamilton in O(2ⁿn²)Exponential, but the right exponential — bitmask DP for Hamiltonian paths, cycles and the travelling salesman.6Knight's Tour and Warnsdorff's RuleA Hamiltonian-cycle problem that is nevertheless constructive — closed tours on every board, and the heuristic that finds one instantly.