Consider a Hamiltonian Graph(G) with no loops and parallel edges. Which of the…
2015
Consider a Hamiltonian Graph(G) with no loops and parallel edges. Which of the following is true with respect to this graph (G)?
(a) \(\deg (v) \geq n/2\) for each vertex of \(G\)
(b) \(\mid E(G) \mid \geq 1/2 (n-1)(n-2)+2\) edges
(c) \(\deg(v) + \deg(w) \geq n\) for every \(𝑣\) and \(𝜔\) not connected by an edge
- A.
(a) and (b)
- B.
(b) and (c)
- C.
(a) and (c)
- D.
(a), (b) and (c)
Attempted by 70 students.
Show answer & explanation
Correct answer: D
Answer summary: None of the three statements is necessarily true for every Hamiltonian simple graph.
Statement (a): The minimum degree being at least n/2 is a sufficient condition for Hamiltonicity (Dirac's theorem) but not a necessary one. Counterexample: an n-vertex cycle is Hamiltonian yet every vertex has degree 2, which is less than n/2 for n ≥ 5.
Statement (b): There is no requirement that a Hamiltonian graph must have that many edges. The n-vertex cycle has exactly n edges, which is much smaller than 1/2 (n-1)(n-2)+2 for n ≥ 5, so (b) can fail.
Statement (c): This is Ore's condition, which is sufficient but not necessary. Again, in an n-vertex cycle two nonadjacent vertices each have degree 2, so their degree sum is 4, which is less than n for n ≥ 5; thus (c) need not hold.
Conclusion: The provided answer asserting all three statements must hold is incorrect. A simple Hamiltonian cycle (for n ≥ 5) provides a direct counterexample to each statement, so none of the three is guaranteed for every Hamiltonian simple graph.