Exercises: Euler Paths, Hamilton Paths, and the Traveling Salesman Problem

DataField.Dev

Exercises: Euler Paths, Hamilton Paths, and the Traveling Salesman Problem

These run from quick degree-counting drills to full proofs, code, modeling, and a conjecture you'll test before you settle. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems live in the appendix answers-to-selected.md — try each one before you peek. Throughout, "graph" allows multigraphs unless stated otherwise, and you may assume a graph is connected (ignoring isolated vertices) whenever an Euler question is asked, just as §30.2 does.

Part A — Warm-ups: count, classify, decide (⭐)

30.1 † A connected graph has degree sequence $2, 2, 4, 4, 6$. Does it have an Euler circuit, an Euler path (that is not a circuit), or neither? Justify in one sentence using Euler's theorem.

30.2 For each connected graph below, state Euler circuit / Euler path / neither by counting odd-degree vertices. (a) Degrees $3, 3, 2, 2$. (b) Degrees $1, 1, 2, 2, 2$. (c) Degrees $3, 3, 3, 3$. (d) Degrees $4, 4, 4, 4, 4$.

30.3 † The complete graph $K_n$ has every vertex of degree $n-1$. For which $n$ does $K_n$ have an Euler circuit? (Give the condition on $n$, and check it against $K_3, K_4, K_5$.)

30.4 Recall (§30.5) that the number of distinct symmetric tours on $n$ cities is $\frac{(n-1)!}{2}$. Compute this for $n = 5, 6, 7$.

30.5 † State the one-word difference between an Euler circuit and a Hamilton circuit: what does each visit exactly once? Then give a graph that has one but not the other, and say which.

30.6 Königsberg had four odd-degree vertices. Suppose the city demolishes the single bridge between the east island $C$ and the west island $D$. Recompute the four degrees and decide whether an Euler path now exists. (Use the degrees from §30.1: $\deg A = \deg B = \deg C = 3$, $\deg D = 5$.)

Part B — Prove it (⭐⭐)

30.7 † (Scaffolded — fill the missing steps.) Prove the necessity half of Euler's theorem for an Euler path: if a connected graph $G$ has an Euler path that is not a circuit, then exactly two vertices have odd degree. Fill in the blanks.

Setup. Let the path start at vertex $s$ and end at a different vertex $t$. Consider any vertex $v$. The path uses each edge of $G$ exactly $\underline{\hphantom{xxx}}$ time(s).
Intermediate vertices. If $v \notin \{s, t\}$, every time the path enters $v$ it later leaves $v$, so the edges at $v$ are consumed in $\underline{\hphantom{xxxxx}}$ pairs; hence $\deg(v)$ is $\underline{\hphantom{xxx}}$.
The endpoints. At $s$, the very first edge is a departure with no matching prior $\underline{\hphantom{xxxxx}}$; at $t$, the very last edge is an arrival with no matching following $\underline{\hphantom{xxxxx}}$. So $s$ and $t$ each have one unpaired edge, making $\deg(s)$ and $\deg(t)$ both $\underline{\hphantom{xxx}}$.
Conclusion. Therefore exactly $\underline{\hphantom{xxx}}$ vertices ($s$ and $t$) have odd degree and all others are even. $\blacksquare$

30.8 Prove: in any graph (Euler or not), the number of odd-degree vertices is even. (Hint: use the handshaking lemma $\sum_v \deg(v) = 2\lvert E\rvert$ from Chapter 27 — split the sum into even-degree and odd-degree vertices.) Then explain in one sentence why this means "exactly one odd-degree vertex" can never happen, so the Euler-path case "exactly two odd" is the smallest nonzero possibility.

30.9 † Prove that the complete graph $K_n$ has a Hamilton circuit for every $n \ge 3$. (This is the fact §30.5 relies on when it says "on a complete graph a Hamilton circuit always exists." A one-line argument suffices — say why any ordering of the vertices works.)

30.10 Prove that a graph $G$ has an Euler path that is not a circuit if and only if $G$ is connected and has exactly two odd-degree vertices. You may cite (not re-prove) the circuit version of Euler's theorem from §30.2 and use this trick: add a temporary edge between the two odd vertices, apply the circuit theorem, then remove that edge. Explain carefully why removing it leaves a valid Euler path.

30.11 † Let $G$ be a graph in which every vertex has even degree, but $G$ is disconnected into two components, each with at least one edge. Prove $G$ has no Euler circuit. (This is the companion to the §30.2 pitfall: "even degrees" alone is not enough.)

30.12 (Uses Dirac's theorem, §30.3.) Let $G$ be a simple graph on $n = 8$ vertices in which every vertex has degree at least $4$. Prove $G$ has a Hamilton circuit. Then exhibit a simple graph on $8$ vertices that is Hamiltonian but has a vertex of degree only $2$ — showing Dirac's condition is sufficient, not necessary.

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Reference solutions are in code/exercise-solutions.py; keep each function to roughly 30 lines or fewer.

30.13 † Write count_odd_degree(adj) that takes an adjacency dict (vertex -> list of neighbors, possibly with repeats for a multigraph) and returns the number of odd-degree vertices. Then write a one-line wrapper euler_kind(adj) that returns "circuit", "path", or "neither" using your count. Show its output on the §30.2 worked-example graph {1: [2, 5, 3], 2: [1, 3], 3: [2, 4, 1, 5], 4: [3, 5], 5: [4, 1, 3]}.

30.14 Implement tour_cost(dist, tour) that takes an $n \times n$ cost matrix and a tour given as a list of city indices that starts and ends at the same city (e.g. [0, 1, 3, 2, 0]), and returns the total cost of traversing it. Test it on the §30.5 matrix D with the optimal tour [0, 1, 3, 2, 0] and confirm it returns 12.

30.15 † Implement is_hamilton_circuit(vertices, edge_set, candidate) that checks whether candidate (a list of vertices beginning and ending at the same vertex) is a valid Hamilton circuit: it must visit every vertex exactly once before returning, and every consecutive pair must be an edge. (edge_set is a set of frozenset({u, v}).) This is the linear-time verifier §30.5 points to when it says "checking is easy." Test it on $K_4$ with candidate = [1, 2, 3, 4, 1] (should be True) and [1, 2, 4, 4, 1] (should be False).

30.16 Implement two_opt_once(dist, tour) that scans for the first 2-opt swap that strictly shortens the given tour, applies it (reversing the segment between the two chosen positions), and returns the improved tour and its cost; if no improving swap exists, return the tour unchanged. Run it once on the nearest-neighbor tour [0, 1, 2, 3, 0] of the §30.5/§30.6 matrix D and report the result. (You are implementing one pass of the local-search heuristic from §30.6.)

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which part fails and why — name the false claim, don't just say "it's wrong."

30.17 † Claim: "This graph has every vertex of even degree, therefore it has an Euler circuit." The graph is two disjoint triangles (six vertices, two separate 3-cycles). "Proof": "Each vertex has degree 2, which is even, and §30.2 says even degree everywhere gives an Euler circuit. ∎" Find the flaw.

30.18 Claim: "Nearest-neighbor returns the optimal TSP tour, because at every step it makes the cheapest possible choice, and a tour built from cheapest choices must be cheapest overall." Using the §30.6 trace on matrix D (nearest-neighbor returns cost 109 while the optimum is 12), explain exactly which sentence of this argument is false and why greedy fails here.

30.19 † Claim: "Hamilton and Euler are the same problem with edges and vertices swapped, so I'll port our $O(V+E)$ Euler-circuit detector into a Hamilton detector by replacing the degree check with a 'visit-count' check, and it'll still run in linear time." (This is the §30.4 Find the Error callout — reconstruct the precise reason the linear-time guarantee does not survive the "swap.")

30.20 Claim: "Christofides guarantees a tour at most $1.5\times$ optimal, so I'll use it on our delivery costs, which include same-day time-window penalties that sometimes make the direct route $A\to C$ cost more than $A\to B\to C$. The $1.5$ guarantee still applies." Find the flaw. (Hint: re-read the hypothesis of Christofides' theorem in §30.6 — what property must the costs satisfy?)

Part E — Model it (⭐⭐⭐)

30.21 † (Model it.) A snowplow operator must clear every street in a small grid neighborhood and return the plow to the depot, driving each street at least once and ideally exactly once. Translate this into a graph problem: what are the vertices, what are the edges, and which of {Euler path, Euler circuit, Hamilton path, Hamilton circuit} is the operator hoping exists? State the exact condition on the street network under which a no-repeats route exists, and explain what the operator must do if some intersections have odd degree (i.e., why they may be forced to replow some streets).

30.22 (Model it.) A genome-assembly pipeline has 200 short DNA reads; two reads are joined by an edge when they overlap enough to be adjacent in the genome, and the assembler wants a single ordering that uses every read exactly once. (a) Is the assembler looking for an Euler or a Hamilton structure, and which one — path or circuit? (b) Given §30.4, what does your answer predict about the computational difficulty of this formulation at scale? (c) The chapter notes a different, tractable assembly formulation exists. Without details, explain what would have to change about the modeling (what becomes the edges) to turn it into an Euler problem instead.

30.23 † (Model it.) A PCB drilling machine must drill 60 holes and return the drill head to its home position, minimizing total head-movement distance; movement cost between any two holes is the straight-line distance (which obeys the triangle inequality). (a) Name the exact problem this is. (b) Is it tractable or NP-hard, and which §30.6 response is appropriate given that the costs are metric? (c) Which heuristic from §30.6 carries a provable quality guarantee here, and what is the guarantee?

30.24 (Model it.) A museum wants a guided-tour route that walks visitors down every corridor exactly once (so they see every exhibit-lined hallway) and returns to the entrance. The floor plan's "junctions" are rooms and its "corridors" are hallways. (a) Which route problem is this? (b) The architect can add one new hallway during renovation. Currently four junctions have an odd number of hallways. Explain, using §30.1–30.2, how a single well-placed new hallway could make the desired route possible, and where it should go.

Part F — Conjecture and test, then prove (⭐⭐⭐)

30.25 † (Conjecture and test, then prove.) You suspect a clean formula for the number of edges in $K_n$, which determines when $K_n$'s Euler status flips. (a) Using the Toolkit Graph (or a plain adjacency dict), build $K_n$ for $n = 3, 4, 5, 6$ and count the edges; tabulate $(n, \lvert E\rvert)$. (b) Conjecture a closed form $\lvert E(K_n)\rvert = ?$. (c) Prove it (a one-line counting argument using $\binom{n}{2}$ from Chapter 17). (d) Use your formula and the parity of $n-1$ to prove the general rule from Exercise 30.3 about when $K_n$ has an Euler circuit.

30.26 (Conjecture and test.) Nearest-neighbor's worst-case overshoot motivates a question: how bad can it get? (a) Write code that, for a family of $4\times 4$ cost matrices you design (vary the single "trap" edge cost like the $100$ in §30.6), computes the ratio nn_cost / optimal_cost. (b) By pushing the trap edge higher and higher, conjecture whether this ratio is bounded (stays below some fixed constant) or unbounded (can be made as large as you like). (c) Argue informally — no formal proof required — why your conjecture holds, connecting to the §30.6 sentence "its tours can be arbitrarily worse than optimal." (This is the Deep Dive teaser from the chapter's Learning Paths.)

30.27 † (Conjecture and test, then prove.) For the cycle graph $C_n$ ($n$ vertices in a ring, each of degree 2): (a) test for small $n$ whether $C_n$ has an Euler circuit and whether it has a Hamilton circuit, using your Part C detectors. (b) Conjecture the answer for general $n$. (c) Prove both claims directly (each is a one- or two-line argument from the definitions). Note that $C_n$ is the example §30.3 uses to show Dirac's theorem is not an "if and only if."

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

30.28 † (Ch. 27 + 30.) State the handshaking lemma (Chapter 27). Then explain, in two or three sentences, how the necessity half of Euler's theorem (each pass through a vertex consumes two edge-ends) is the local counterpart of the handshaking lemma's global statement $\sum_v \deg(v) = 2\lvert E\rvert$.

30.29 (Ch. 28 + 30.) Euler's theorem requires the graph to be connected. (a) Which Chapter 28 traversal would you run, and from where, to verify connectivity before applying Euler's theorem? (b) What is its time complexity, and why does combining it with the $O(V+E)$ degree count keep the whole "does an Euler circuit exist?" decision tractable? (c) Contrast this total cost with the $\frac{(n-1)!}{2}$ of brute-force TSP in one sentence.

30.30 † (Ch. 6 + 30.) The sufficiency proof of Euler's theorem (§30.2) is by strong induction on the number of edges. (a) Identify the base case and the inductive hypothesis as they appear in the proof. (b) Pinpoint the single sentence in the proof where the inductive hypothesis is actually applied. (c) Explain why strong induction (assume the result for all smaller edge-counts), rather than ordinary induction (assume only the immediately previous case), is the right tool here — tie it to the Chapter 6 / Chapter 7 distinction.

30.31 (Ch. 17 + 30.) The brute-force counts in §30.4–30.5 are permutation counts. (a) Explain why fixing the start city reduces the number of tours from $n!$ to $(n-1)!$, using the language of Chapter 17 (a tour is a cyclic arrangement). (b) Explain why symmetric costs halve it again to $\frac{(n-1)!}{2}$. (c) Compute the number of distinct symmetric tours for $n = 10$ and compare it to the $O(n^2 2^n)$ work of Held–Karp at $n = 10$ — which is smaller, and what does that foreshadow about which method wins as $n$ grows?

30.32 (Ch. 14 + 30 — Deep Dive.) The chapter claims Euler detection is $O(V+E)$ while Hierholzer's construction is also $O(V+E)$. (a) Justify the construction's bound: argue that each edge is pushed onto and popped off the stack a constant number of times. (b) Using the asymptotic language of Chapter 14, explain precisely what it means that $O(V+E)$ is "polynomial in the input size" whereas $O(2^n)$ (Held–Karp) and $O(n!)$ (brute force) are not, and why that single distinction is the "threshold concept" of §30.4.

30.33 (Deep Dive.) Decision-vs-optimization. §30.5 states that an oracle for decision TSP ("is there a tour of cost $\le B$?") could be used to solve optimization TSP by binary search on the budget $B$. (a) Sketch this reduction: how many calls to the decision oracle, as a function of the range of possible tour costs, does the binary search need? (b) Argue that this number is polynomial in the input size, so the two forms "stand or fall together" on tractability. (c) In one sentence, say why this is exactly why Chapter 37 can phrase its whole theory in terms of decision problems without losing the practical optimization question.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a clearly stated claim, correct use of the connectivity and parity conditions where Euler is involved, explicit appeal to the inductive hypothesis where induction is used, and — for modeling problems — a clean statement of what the vertices and edges are before any theorem is invoked.