Consider a Hamiltonian Graph \(G\) with no loops or parallel edges and with…
2017
Consider a Hamiltonian Graph \(G\) with no loops or parallel edges and with \(|V(G)| = n ≥ 3\). Then which of the following is true ?
- A.
\(\text{deg}\left ( v \right )\geq \frac{n}{2}\)for each vertex\(v\\\) - B.
\(\left | E\left ( G \right ) \right |\geq \frac{1}{2}\left ( n-1 \right )\left ( n-2 \right )+2 \\\) - C.
\(\text{deg}\left ( v \right )+\text{deg}\left ( w \right )\geq n\)whenever\(𝑣\)and\(𝑤\)are not connected by an edge - D.
All of the above
Attempted by 81 students.
Show answer & explanation
Correct answer: D
Answer: None of the listed statements is necessarily true for every Hamiltonian graph. Therefore the choice that all statements always hold is incorrect.
Reason and counterexamples:
Statement: minimum degree at least n/2 for every vertex.
Counterexample: The cycle graph on n vertices has degree 2 at every vertex and is Hamiltonian. For n ≥ 5 we have 2 < n/2, so the inequality fails. Note that Dirac's theorem states this minimum-degree condition is sufficient (if it holds then the graph is Hamiltonian) but it is not necessary.
Statement: the edge-count bound |E(G)| ≥ (n-1)(n-2)/2 + 2.
Counterexample: The cycle on n vertices has |E| = n, which is typically much smaller than the right-hand side. For example, when n = 6 we have |E| = 6 but the bound gives 12, so the inequality does not hold for this Hamiltonian graph.
Statement: for every pair of non-adjacent vertices v and w, deg(v) + deg(w) ≥ n.
Counterexample: In the 6-cycle each vertex has degree 2; pick two non-adjacent vertices and their degree sum is 4 < 6, yet the graph is Hamiltonian. Ore's theorem gives this degree-sum condition as a sufficient condition, but it is not necessary.
Conclusion: Each of the three listed statements is a well-known sufficient condition for Hamiltonicity (Dirac, Ore, and certain edge-count bounds), but none is required for every Hamiltonian graph. A correct answer to the original question would state that none of the given conditions must always hold.