Questions: Hamiltonian Circuits and Paths

Question 1

A graph G has 10 vertices. Dirac's theorem guarantees a Hamiltonian circuit if which condition holds?

• A. G is connected and has at least 10 edges
• B. Every vertex has degree at least 5
• C. Every pair of non-adjacent vertices has combined degree at least 10
• D. G has an Eulerian circuit

Answer: (B)

Dirac's theorem states: if a graph on n ≥ 3 vertices has every vertex with degree ≥ n/2, then a Hamiltonian circuit exists. For n = 10, the threshold is 10/2 = 5. Option C is Ore's theorem (a different sufficient condition). Option D (Eulerian circuit) has no bearing on Hamiltonian circuits — these are entirely different properties.

Question 2

You check a graph G and find that Dirac's condition fails — some vertex has degree below n/2. What can you conclude?

• A. G has no Hamiltonian circuit
• B. G may or may not have a Hamiltonian circuit — Dirac's is a sufficient condition, not a necessary one
• C. G has no Eulerian circuit either
• D. G is disconnected

Answer: (B)

Dirac's theorem provides a *sufficient* condition for Hamiltonian circuits, not a necessary one. A graph can have a Hamiltonian circuit even when Dirac's condition fails. Failing a sufficient condition tells you the theorem's guarantee doesn't apply — it says nothing about what is actually true of the graph. This is the most important distinction: sufficient conditions confirm existence when met, but their failure confirms nothing.

Question 3

A connected graph has a Hamiltonian circuit if and only if most vertex has even degree.

• T. True
• F. False

Answer: False

The 'every vertex has even degree' condition characterizes *Eulerian* circuits, not Hamiltonian circuits. An Eulerian circuit traverses every edge exactly once; a Hamiltonian circuit visits every vertex exactly once. These are fundamentally different conditions. Hamiltonian circuits have no known simple necessary and sufficient characterization — determining their existence is NP-complete.

Question 4

Determining whether an arbitrary graph has a Hamiltonian circuit is computationally harder than determining whether it has an Eulerian circuit.

• T. True
• F. False

Answer: True

Eulerian circuits have a polynomial-time characterization: check connectivity and verify all vertices have even degree — a linear-time computation. Hamiltonian circuit existence is NP-complete: no polynomial-time algorithm is known, and the problem is believed to require exponential time in the worst case. Despite the surface similarity of the two questions, the vertex version is exponentially harder than the edge version.

Question 5

Why does the degree-based characterization that works for Eulerian circuits not extend to Hamiltonian circuits?

Model answer: Eulerian circuits can be checked locally: at each vertex, whether the circuit can continue depends only on the parity of that vertex's degree, which is a purely local property. Hamiltonian circuits require global coordination — choosing the wrong vertex early can trap you with unreachable vertices later, and there is no local signal that warns you before it happens.

The local vs. global distinction is the core insight. Euler's condition works because you can always 'fix' a locally bad choice by rerouting — the even-degree condition ensures you never get permanently stuck. Hamiltonian paths require thinking about the entire graph simultaneously: does this sequence of vertex visits leave a connected remainder that can be completed? That global feasibility check has no known efficient shortcut, which is why it's NP-complete while Eulerian circuit detection is easy.