An algorithm claims to verify a proposed Hamiltonian cycle in O(n) time by checking that every vertex appears exactly once and each consecutive pair is connected by an edge. Is this consistent with the NP-completeness of the Hamiltonian cycle problem?
ANo — if verification is O(n), then finding a Hamiltonian cycle must also be O(n) by symmetry
BYes — NP-completeness says finding a solution may be hard, but verification is always easy; the Hamiltonian cycle problem is in NP precisely because valid solutions can be verified in polynomial time
CNo — NP-complete problems cannot be verified in polynomial time; that is what makes them hard
DYes, but only for graphs with fewer than 1,000 vertices; larger graphs require exponential verification time
The NP in 'NP-complete' stands for 'nondeterministic polynomial time' — the class of problems where proposed solutions can be verified in polynomial time. NP-completeness says that *finding* a solution appears to require exponential time; *verifying* a given solution is quick. For Hamiltonian cycle, checking that every vertex appears exactly once and all edges exist takes O(n) time. This verification asymmetry — easy to check, hard to find — is the defining characteristic of NP. Option C is exactly backwards and is the most common misconception about what 'NP-complete' means.
Question 2 Multiple Choice
An undirected graph G has 15 vertices, all with even degree. What can you conclude?
AG contains a Hamiltonian cycle — every vertex with even degree guarantees each can be visited exactly once
BG contains a Hamiltonian cycle if and only if it is also connected
CG contains an Eulerian circuit — a closed walk traversing every edge exactly once — if G is connected
DG contains neither an Eulerian circuit nor a Hamiltonian cycle without further information
This is Euler's theorem: a connected graph has an Eulerian circuit if and only if every vertex has even degree. If G is connected and all vertices have even degree, an Eulerian circuit exists and can be found in polynomial time. Crucially, the even-degree condition says nothing about a Hamiltonian cycle. The Hamiltonian cycle problem — visiting every vertex once — has no such clean characterization and is NP-complete. This contrast is the key lesson: 'every edge once' (Eulerian) admits a polynomial-time solution with a simple necessary and sufficient condition; 'every vertex once' (Hamiltonian) is NP-complete with no known efficient algorithm.
Question 3 True / False
The Eulerian circuit problem and the Hamiltonian cycle problem both ask about traversal conditions on graphs, yet one is solvable in polynomial time while the other is NP-complete.
TTrue
FFalse
Answer: True
Eulerian circuit (traverse every edge exactly once): solvable in polynomial time using Euler's theorem (all vertices must have even degree) and Hierholzer's algorithm. Hamiltonian cycle (visit every vertex exactly once): NP-complete, with no known polynomial-time algorithm. This striking contrast illustrates how small changes in problem formulation — edges vs. vertices — can produce enormous changes in computational complexity. The lesson is that problem hardness is not determined by how simple the problem sounds, but by the mathematical structure it requires you to exploit.
Question 4 True / False
Because the Hamiltonian cycle problem is NP-complete, it has been proven that no polynomial-time algorithm for it can ever exist.
TTrue
FFalse
Answer: False
NP-completeness does not prove that no polynomial-time algorithm exists — it proves that if any NP-complete problem has a polynomial-time solution, then P = NP (every NP problem would be tractable). Since we do not know whether P = NP, we cannot rule out a polynomial-time algorithm for Hamiltonian cycle. NP-completeness provides strong evidence that efficient algorithms are unlikely, but it is not a proof of impossibility. The P ≠ NP conjecture is one of the Millennium Prize Problems — unresolved despite decades of effort. What NP-completeness does tell us is that we should abandon the search for exact polynomial-time algorithms and turn to approximations, heuristics, or special-case structure instead.
Question 5 Short Answer
Why does changing a problem from 'traverse every edge exactly once' to 'visit every vertex exactly once' transform it from polynomial-time solvable to NP-complete?
Think about your answer, then reveal below.
Model answer: The Eulerian condition has a clean algebraic characterization: an Eulerian circuit exists if and only if every vertex has even degree, which can be checked in O(n) time. This structure allows a polynomial-time algorithm. The Hamiltonian condition has no analogous characterization — there is no known property of a graph that you can check cheaply and that determines whether a Hamiltonian cycle exists. You must, in the worst case, reason about whether some permutation of all n vertices forms a valid cycle, which leads to a search space of (n−1)! possibilities. The underlying combinatorial structure simply doesn't offer the same algebraic shortcuts.
This example is a favorite in computability theory because the two problems sound nearly identical to non-specialists. The key insight is that computational difficulty is not about how simple the problem *sounds* but about what mathematical structure it has. Eulerian problems have degree-sequence characterizations that reduce the question to local properties; Hamiltonian problems require reasoning about global structure that no efficient algorithm has exploited. This is why NP-completeness proofs are valuable: they tell us when we are facing a fundamentally hard problem and should look for approximations rather than exact solutions.