Questions: Hamiltonian Cycles: Sufficient Conditions and Challenges

Question 1

A simple graph G has n = 10 vertices and every vertex has degree exactly 4. Does Dirac's theorem guarantee that G has a Hamiltonian cycle?

• A. Yes — every vertex has degree 4 > 3, which is close enough to n/2 = 5
• B. No — Dirac's theorem requires minimum degree ≥ n/2, and here min degree 4 < 5
• C. Yes — Dirac's theorem applies whenever every vertex has the same degree
• D. No — Dirac's theorem only applies to complete graphs

Answer: (B)

Dirac's theorem requires minimum degree ≥ n/2. With n = 10, the threshold is n/2 = 5. A minimum degree of 4 falls below it, so Dirac's theorem gives no guarantee. The graph might still have a Hamiltonian cycle — but not because of Dirac's theorem. This is a common off-by-one mistake; the condition is strict.

Question 2

The cycle graph C₁₀ has 10 vertices, every vertex has degree 2, and it clearly has a Hamiltonian cycle (the graph itself is one). Yet n/2 = 5, so every vertex's degree is far below the Dirac threshold. What does this tell us?

• A. Dirac's theorem must be incorrect for regular graphs
• B. Dirac's theorem gives a sufficient condition, not a necessary one — graphs can have Hamiltonian cycles without satisfying the degree threshold
• C. C₁₀ does not actually qualify as a Hamiltonian cycle because cycles are not graphs
• D. Dirac's theorem only applies when the minimum degree equals exactly n/2

Answer: (B)

A sufficient condition guarantees the conclusion when the condition is met, but the conclusion can also hold when it is not. C₁₀ demonstrates this: it fails Dirac's condition badly yet has a trivial Hamiltonian cycle. This is the essential asymmetry — Dirac's theorem cannot be used to rule out Hamiltonian cycles, only to confirm them in dense graphs.

Question 3

Determining whether an arbitrary graph has a Hamiltonian cycle is an NP-complete problem.

• T. True
• F. False

Answer: True

Unlike Eulerian circuits — which have an efficient polynomial-time algorithm — Hamiltonicity is NP-complete in general. No polynomial-time algorithm is known, and if one existed, it would imply P = NP. This is why the sufficient conditions (Dirac, Ore) are practically useful: they identify structural cases where we can confirm Hamiltonicity efficiently without solving the general problem.

Question 4

If a graph fails to satisfy Dirac's theorem (some vertex has degree less than n/2), then it cannot contain a Hamiltonian cycle.

• T. True
• F. False

Answer: False

Dirac's theorem states that meeting the degree condition is sufficient for a Hamiltonian cycle to exist. It says nothing about what happens when the condition fails. Cycle graphs Cₙ fail the Dirac condition for n ≥ 5 yet obviously have Hamiltonian cycles. Sufficient conditions only guarantee from one direction — they cannot be contraposed to rule out the conclusion.

Question 5

Eulerian circuits and Hamiltonian cycles both involve traversing a graph completely, but they differ dramatically in computational difficulty. What is the key distinction, and why does it matter?

Model answer: An Eulerian circuit traverses every edge exactly once; a Hamiltonian cycle visits every vertex exactly once. Eulerian circuits have a clean necessary-and-sufficient characterization (connected, all even degrees) and can be found in polynomial time. Hamiltonicity has only sufficient conditions and is NP-complete in general. The distinction matters because nearly identical-sounding combinatorial problems can differ enormously in tractability — Hamiltonicity is one of the founding NP-complete problems.

This contrast is a central lesson in complexity theory: structural similarity at the informal description level does not predict algorithmic difficulty. Edge-traversal problems are often tractable; vertex-traversal problems are typically hard. Recognizing this difference guards against assuming that any 'visit everything' problem can be solved efficiently.