Self-Assessment Quiz: Euler Paths, Hamilton Paths, and the Traveling Salesman Problem

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

An Euler circuit in a connected graph exists if and only if:

A) exactly two vertices have odd degree B) every vertex has even degree C) every vertex has the same degree D) the graph has no cycles

Question 2

An Euler path that is not a circuit exists in a connected graph if and only if the number of odd-degree vertices is:

A) 0 B) exactly 1 C) exactly 2 D) any even number

Question 3

The single most important word-level difference between an Euler circuit and a Hamilton circuit is that an Euler circuit visits every _ exactly once, while a Hamilton circuit visits every _ exactly once.

A) vertex; edge B) edge; vertex C) face; vertex D) edge; face

Question 4

The Königsberg bridge problem had no solution because:

A) the graph was disconnected B) all four landmasses had odd degree (four > two) C) it was a multigraph, and Euler's theorem doesn't apply to multigraphs D) there were too many bridges

Question 5

Which best describes why deciding whether an Euler circuit exists is tractable?

A) Euler circuits are always short B) Existence reduces to counting odd-degree vertices — an $O(V+E)$ scan, no route search C) There is only ever one Euler circuit, so you just print it D) Hierholzer's algorithm is exponential but usually fast

Question 6

For the Traveling Salesman Problem on $n$ cities, the number of distinct symmetric tours is:

A) $n!$ B) $(n-1)!$ C) $\frac{(n-1)!}{2}$ D) $2^n$

Question 7

Which statement about the complexity of the Hamilton circuit problem is accurate as presented in this chapter?

A) It is solvable in $O(V+E)$ by a degree count, just like Euler B) No polynomial-time algorithm is known; it is NP-hard C) It has been proven to require exponential time D) It is undecidable

Question 8

Dirac's theorem states that a simple graph on $n \ge 3$ vertices with every vertex of degree at least $n/2$ has a Hamilton circuit. This theorem is:

A) an "if and only if" characterization of Hamiltonicity B) a sufficient condition only — it can say "yes," never "no" C) a necessary condition only D) false

Question 9

A TSP tour is, structurally, a:

A) Hamilton circuit on the complete weighted graph of cities B) Euler circuit on the complete weighted graph of cities C) shortest path between two cities D) minimum spanning tree

Question 10

The nearest-neighbor heuristic for TSP:

A) always returns the optimal tour B) runs in $O(n^2)$ and returns a tour that can be arbitrarily worse than optimal C) runs in $O(n!)$ but guarantees a tour within $1.5\times$ optimal D) only works on metric instances

Question 11

Christofides' algorithm guarantees a tour at most $\frac{3}{2}$ times optimal, but only for:

A) any TSP instance B) metric TSP — instances whose costs satisfy the triangle inequality C) instances with fewer than 25 cities D) symmetric instances only, metric or not

Question 12

Given a proposed TSP tour and a claimed cost bound \$B, how long does it take to verify the tour costs at most \$B?

A) $O(n!)$ B) $O(2^n)$ C) $O(n)$ — sum the edge costs along the tour D) it cannot be verified efficiently

Question 13

Held–Karp dynamic programming solves TSP exactly in $O(n^2 2^n)$ time. Compared with brute force, this means Held–Karp:

A) makes TSP tractable for arbitrarily large $n$ B) is dramatically faster than $O(n!)$ but still exponential — it moves the wall from ~12 to ~25 cities C) is slower than brute force D) only finds approximate tours

Question 14

Which response to an NP-hard problem provides a proven bound on solution quality in polynomial time?

A) brute force B) nearest-neighbor C) an approximation algorithm such as Christofides D) Held–Karp

Question 15 (True/False, justify)

True or false: If a connected graph has every vertex of even degree, it must have an Euler circuit. Justify in one sentence.

Question 16 (True/False, justify)

True or false: If a graph has a Hamilton circuit, it must also have an Euler circuit. Justify in one sentence (a small example or counterexample is ideal).

Question 17 (True/False, justify)

True or false: Buying a computer 1000 times faster lets brute-force TSP handle roughly 1000 times as many cities. Justify in one sentence.

Question 18 (Short answer)

State the two conditions a graph must satisfy for an Euler circuit to exist. (Both are required.)

Question 19 (Short answer)

In one sentence, explain the "verify/find gap" that the chapter says is "the heart of P vs. NP," using TSP as the example.

Question 20 (Short answer)

List, in order from "exact but only small $n$" to "fast but no guarantee," the three responses to NP-hardness from the chapter's response menu, with one example of each.

Answer Key

Topics to review by question