Questions: Hamiltonian Paths, Cycles, and NP-Completeness

Question 1

A graph has exactly two vertices of odd degree. A student concludes it must have a Hamiltonian path. What is wrong with this reasoning?

• A. Nothing is wrong — two odd-degree vertices guarantee a Hamiltonian path
• B. Two odd-degree vertices guarantee an Eulerian path, not a Hamiltonian path — these are different problems with different criteria
• C. The student should check whether it has zero odd-degree vertices, which would guarantee a Hamiltonian cycle
• D. Degree conditions can only rule out Hamiltonian paths, never guarantee them

Answer: (B)

Two odd-degree vertices is exactly the condition for an Eulerian path (traversing every edge once), not a Hamiltonian path (visiting every vertex once). Confusing these is the central misconception: Eulerian paths have a clean degree-based characterization, Hamiltonian paths do not. The student has applied the right kind of test to the wrong problem. A graph can have two odd-degree vertices and either contain or lack a Hamiltonian path.

Question 2

What does it mean practically that the Hamiltonian cycle problem is NP-complete?

• A. No algorithm can solve it — it is mathematically undecidable
• B. It can be solved in polynomial time only for graphs with special structure, but no known polynomial-time algorithm works for all graphs
• C. The problem is harder than any problem in NP, making it the most difficult class of problems
• D. It requires exponential space to store the graph, making it infeasible for large inputs

Answer: (B)

NP-completeness means no known polynomial-time algorithm solves it in the worst case, and it is as hard as every other NP problem. It is NOT undecidable — a brute-force algorithm can always solve it by checking all possible vertex orderings, which takes O(n!) time. The practical consequence is that for large graphs, no efficient general solution is known. Option C is wrong: NP-complete problems are in NP, not harder than NP (that would be NP-hard but not in NP, or higher levels of the polynomial hierarchy).

Question 3

Any graph satisfying Dirac's condition (every vertex has degree ≥ n/2) is guaranteed to contain a Hamiltonian cycle.

• T. True
• F. False

Answer: True

Dirac's theorem (1952) states exactly this: if G is a simple graph with n ≥ 3 vertices and every vertex has degree ≥ n/2, then G contains a Hamiltonian cycle. This is one of the few positive sufficient conditions for Hamiltonian cycles. Note that it is a sufficient but not necessary condition — graphs can have Hamiltonian cycles with much lower degree requirements. Dirac's condition is also useful precisely because it is checkable in polynomial time, unlike the Hamiltonian problem itself.

Question 4

If a graph contains an Eulerian circuit, it should also contain a Hamiltonian cycle.

• T. True
• F. False

Answer: False

These properties are completely independent. An Eulerian circuit (traversing every edge once and returning to the start) requires all vertices to have even degree. A Hamiltonian cycle (visiting every vertex once and returning) requires the right global structure but has no simple degree characterization. A complete graph K₃ (triangle) has both; a graph like two triangles sharing a single vertex has an Eulerian circuit but no Hamiltonian cycle (the shared vertex would have to be visited twice). The contrast between these problems is one of the most instructive examples in combinatorics.

Question 5

Explain why the Eulerian path problem is 'easy' (polynomial time) while the Hamiltonian path problem is 'hard' (NP-complete), even though both involve traversing graphs.

Model answer: Eulerian paths are easy because they have a local, degree-based characterization: you only need to count vertex degrees to decide existence, and construction follows Hierholzer's algorithm. Hamiltonian paths require global structure — whether a path visiting every vertex exists cannot be determined by any local property like degree. No short certificate for the absence of a Hamiltonian path exists, and exhaustive search takes exponential time. The contrast shows that seemingly similar problems can have radically different computational complexities based on what structural information is needed.

The difficulty gap between Eulerian and Hamiltonian problems is a clean illustration of why P ≠ NP (if true). Eulerian paths reduce to a local property (degree sequence), while Hamiltonian paths require checking a fundamentally global combinatorial structure. This is why NP-completeness proofs often reduce from Hamiltonian cycle — it is a canonical hard problem precisely because it lacks the local structure that makes other graph problems tractable.