Chapter 30 — Key Takeaways

Euler Paths, Hamilton Paths, and the Traveling Salesman Problem — the reread-before-the-exam card.

The one-word difference

Mnemonic: Euler = Edges; Hamilton = visit every point/place (vertex).

Named results & facts at a glance

Key numbers to memorize:

• Euler/Hamilton/TSP existence test costs: Euler $= O(V+E)$; Hamilton/TSP $=$ no known polynomial.
• Distinct symmetric tours on $n$ cities $= \dfrac{(n-1)!}{2}$.
• $K_n$: degree of every vertex $= n-1$; Euler circuit ⇔ $n$ odd; Hamilton circuit always (for $n\ge3$).
• A valid graph degree sequence has an even number of odd-degree vertices (handshaking) — so "exactly 1 odd vertex" or "exactly 3" is impossible.

Euler's Theorem (THE result of this chapter)

For a connected graph/multigraph with $\ge 1$ edge:

• Decision cost: $O(V+E)$ — just count odd-degree vertices. No search.
• Connectivity is required — check it (BFS/DFS) in addition to the parity rule.
• Königsberg: 4 odd-degree vertices ⇒ no Euler path. (Euler, 1736 — birth of graph theory.)

Proof skeleton: - Necessity (only-if): parity argument — each pass through a vertex uses edges in in/out pairs ⇒ even degree. (Local version of the handshaking lemma, $\sum_v \deg(v)=2|E|$.) - Sufficiency (if): constructive (Hierholzer, strong induction on edge count) — walk until you return to start (even degree ⇒ never stuck elsewhere; an arrival elsewhere would make an odd # of used edges at an even-degree vertex), then splice leftover subtours into the gaps (connectivity guarantees a splice point). This is the $O(V+E)$ algorithm.

Decision recipe (do this on any "traverse every edge" problem):

1. Is the graph connected (ignore degree-0 vertices)? If not → no Euler path/circuit. (Run BFS/DFS.)
2. Count vertices of odd degree $\to k$.
3. $k = 0$ → Euler circuit (start anywhere). $k = 2$ → Euler path (start/end at the two odd ones). $k > 2$ (always even, never odd — handshaking) → neither.

Worked check — degree sequences (connected):

Hamilton & Dirac

• No known efficient characterization of Hamiltonicity (unlike Euler). Best general method = search/backtracking (exponential).
• Dirac's theorem (sufficient, NOT iff): simple graph, $n\ge 3$, every vertex degree $\ge n/2$ ⇒ Hamilton circuit exists.
• One-way only: a graph can fail Dirac and still be Hamiltonian (e.g. cycle $C_n$, all degrees 2).
• $K_n$ ($n\ge 3$) always has a Hamilton circuit (all edges exist). $K_n$ has an Euler circuit iff $n$ is odd (each degree $n-1$ even ⇔ $n$ odd).

TSP

• Definition: cheapest tour visiting every city once, returning to start = min-cost Hamilton circuit on complete weighted graph.
• # distinct tours (symmetric costs): $\dfrac{(n-1)!}{2}$.
• Two forms: optimization (find best tour — NP-hard) vs. decision (tour of cost $\le B$? — NP-complete, Ch.37). Binary-search the budget links them.
• Verify vs. find: checking a proposed tour's cost = $O(n)$ (easy ⇒ in NP); finding the optimum = apparently exponential. ← the P-vs-NP drama.

The tractable/intractable boundary (🚪 threshold)

Brute-force TSP wall-clock (at $10^9$ tours/sec, $\approx(n-1)!$):

Hardware can't fix exponential/factorial: $1000\times$ faster moves brute-force TSP from ~25 to ~27 cities. Held–Karp DP ($O(n^2 2^n)$) pushes the wall to ~25, not to thousands.

NP-hard (preview, formalized Ch.37): - = at least as hard as everything in NP. Hamilton circuit and TSP are NP-hard. - A fast algorithm for one NP-hard problem ⇒ fast for all. None known ⇒ believed impossible (P vs. NP, \$1M Millennium Prize).

Decision rule: "I have a route problem — what do I do?"

Is it "use every EDGE once"?      -> EULER. Count odd-degree vertices. O(V+E). DONE.
Is it "visit every VERTEX once"?  -> HAMILTON / TSP.  NP-hard.  Do NOT brute-force at scale.
   |
   +-- n small (<~12), need exact?      -> brute force (n-1)!/2 tours
   +-- n moderate (<~25), need exact?   -> Held-Karp DP  O(n^2 * 2^n)
   +-- need a PROVEN-close tour (metric)-> Christofides  (<= 3/2 * optimal, polynomial)
   +-- need fast, "usually good"?       -> nearest-neighbor O(n^2), then 2-opt local search

Coping menu for NP-hard problems

• Heuristic = fast, gives up optimality guarantee. Approximation algorithm = heuristic with a proven bound.
• Greedy ≠ optimal here. Nearest-neighbor can be arbitrarily bad. (Contrast Dijkstra Ch.29 / MST Ch.32, where greedy is optimal.)
• 2-opt = local search: remove 2 edges, reconnect (reverse a segment), keep if shorter; iterate to a local optimum. Uncrosses tour "X" crossings.

Common pitfalls

Toolkit additions (graphs.py, builds on Ch.27–29)

Toolkit deliberately stops at Euler (tractable). No efficient Hamilton/TSP solver exists — a later checkpoint adds the nearest-neighbor heuristic instead.

One-line definitions (this chapter's reserved terms)

• Euler path — trail using every edge once; ⇔ exactly two odd-degree vertices.
• Euler circuit — closed Euler path; ⇔ all degrees even.
• Hamilton path — visits every vertex once; no efficient existence test known.
• Hamilton circuit — closed Hamilton path (Hamilton cycle); existence is NP-hard.
• TSP — minimum-cost Hamilton circuit on a complete weighted graph.
• NP-hard (preview, Ch.37) — at least as hard as everything in NP; no known polynomial algorithm.
• heuristic — fast method with no optimality guarantee; an approximation algorithm is a heuristic with a proven bound.

Exam self-test (cover the answers)

1. Graph with degrees $4,4,3,3,2$, connected — Euler circuit, path, or neither? → path (two odd).
2. Does $K_6$ have an Euler circuit? → No (degree 5 = odd; $n=6$ even). Hamilton circuit? → Yes.

3. distinct tours, 7 cities? → $(7-1)!/2 = 720/2 = \mathbf{360}$.

4. Nearest-neighbor is $O(n^2)$ and fast — is it optimal? → No, can be arbitrarily far from optimal.
5. Why is decision-TSP in NP? → a proposed tour is checkable in $O(n)$ (sum costs, compare to budget).

Cross-references

• Builds on: Ch.27 (graph terms, degree, $K_n$, handshaking lemma), Ch.28 (DFS/BFS, connectivity, $O(V+E)$ traversal).
• Sets up: Ch.33 (coloring, planarity, Euler's formula), Ch.37 (P, NP, NP-complete — TSP formalized).