Further Reading: Euler Paths, Hamilton Paths, and the Traveling Salesman Problem

Annotated pointers for going deeper. Start with the textbook sections to firm up Euler's theorem and the Euler/Hamilton distinction, then branch toward whichever pulls you: the theory of why TSP is hard (which Chapter 37 will formalize), the algorithms for coping with it, or the history of the problem that arguably launched two fields at once.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §10.5 ("Euler and Hamilton Paths") The market-standard treatment, matching this chapter's framing closely: Euler's theorem with proof, the Königsberg origin, Hamilton paths/circuits, and a clear statement that no efficient Hamiltonicity test is known. The exercise bank is large and well-graded — the first place to go for more drill.

West, Introduction to Graph Theory (2nd ed.), the Eulerian-graphs and Hamiltonian-graphs sections A more mathematically rigorous home for the same results, including a clean proof of Euler's theorem and a careful treatment of Dirac's and Ore's sufficient conditions for Hamiltonicity. Read this when you want the theorems stated and proved at full strength.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the Euler-paths section Freely available. A gentle, example-driven walk through Euler circuits and the odd-degree counting argument, with interactive-style problems. A good companion if Rosen feels terse.

On why Hamilton/TSP is hard (the bridge to Chapter 37)

Sipser, Introduction to the Theory of Computation (3rd ed.), Chapter 7 (P, NP, NP-completeness) The canonical, readable account of the complexity classes this chapter only previews. Read it after this chapter and before Chapter 37 to see "NP-hard" turned from an informal label into a precise theorem — including the Hamiltonian-path problem and TSP as worked examples of NP-completeness.

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), the NP-completeness and approximation-algorithms chapters Covers both halves of this chapter's punchline: the NP-completeness machinery, and the approximation-algorithm chapter that proves the Christofides-style guarantees (including the metric-TSP $\frac{3}{2}$-approximation and why the triangle inequality is essential). The standard algorithms reference for the "coping with hardness" menu of §30.6.

On the algorithms of §30.6 (heuristics and exact solvers)

CLRS (4th ed.), the minimum-spanning-tree and matching material (Chapters referenced in 32 & 34) Christofides' algorithm is built from a minimum spanning tree plus a minimum-weight perfect matching. Reading the MST chapter now (and the matching material after Chapter 34) demystifies how a polynomial algorithm can come with a provable quality bound — the "approximation with a proof" idea of §30.6.

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), §2.2.1 (stacks) and the backtracking discussions Background for the data structures behind Hierholzer's Euler-circuit construction (the stack-based walk of the Project Checkpoint) and for the backtracking search that any exact Hamiltonian solver must fall back on. Useful when you want to understand the implementation, not just the existence theorems.

History and perspective

Euler's 1736 paper, "Solutio problematis ad geometriam situs pertinentis" (commonly attributed; widely reprinted in translation) The founding document of graph theory: Euler's own resolution of the Königsberg bridge problem. Many accessible English translations and summaries exist; reading even a summary shows how radical the "abstract away geometry, keep only connections" move was in 1736 (theme three of the book — abstraction).

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), the material on permutations and counting Not about graphs directly, but the cleanest source for the permutation- and cycle-counting that makes the $(n-1)!/2$ tour count of §30.5 precise. Save it for after Chapter 17 (counting) if you want the combinatorics behind "why brute force is factorial" nailed down rigorously.

Suggested order

  1. Re-read §§30.1–30.2 here, then do Rosen §10.5 exercises for drill on Euler's theorem.
  2. Read Levin's Euler section (free) if you want a gentler second pass; read West's proofs if you want a stronger one.
  3. Read CLRS's approximation-algorithms chapter to see the Christofides guarantee proved — the natural sequel to §30.6.
  4. Save Sipser Chapter 7 (or CLRS's NP-completeness chapter) for the run-up to Chapter 37, where this chapter's informal "NP-hard" becomes a theorem.
  5. For fun and perspective, read a translation/summary of Euler's 1736 paper at any point — it is short and astonishingly modern.