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
Answer: D. (a), (b) and (c) — Concept: For a simple graph G on n ≥ 3 vertices (no loops or parallel edges), several classical theorems state SUFFICIENT — not necessary — conditions for G…
- A.
(a) and (b)
- B.
(b) and (c)
- C.
(a) and (c)
- D.
(a), (b) and (c)
Attempted by 115 students.
Show answer & explanation
Correct answer: D
Concept: For a simple graph G on n ≥ 3 vertices (no loops or parallel edges), several classical theorems state SUFFICIENT — not necessary — conditions for G to contain a Hamiltonian cycle: Dirac's theorem (minimum degree deg(v) ≥ n/2 at every vertex), the edge-density theorem (|E(G)| ≥ (n−1)(n−2)/2 + 2, exactly one edge more than the largest edge count any non-Hamiltonian graph on n vertices can have), and Ore's theorem (deg(v) + deg(w) ≥ n for every pair of vertices v, w not joined by an edge). Each is a one-way implication — meeting the bound guarantees Hamiltonicity, but a Hamiltonian graph is not required to meet it.
Application: Check each statement against its known theorem:
Statement (a) is exactly Dirac’s theorem: threshold n/2, the correct constant.
Statement (b) is exactly the edge-density theorem: the extremal non-Hamiltonian graph on n vertices is Kn−1 plus one pendant vertex attached to a single vertex of Kn−1 — it has (n−1)(n−2)/2 + 1 edges and is not Hamiltonian because the pendant vertex has degree 1; one edge beyond that maximum, (n−1)(n−2)/2 + 2, is exactly the stated threshold.
Statement (c) is exactly Ore’s theorem: threshold n on the degree sum of a non-adjacent pair, the correct constant.
Cross-check: The n-vertex cycle Cn (n ≥ 5) is a Hamiltonian graph satisfying NONE of (a), (b), (c) — every vertex has degree 2 (< n/2), it has only n edges (< (n−1)(n−2)/2 + 2), and any two non-adjacent vertices have degree sum 4 (< n). This is expected and does not contradict any of the three theorems: a sufficient-condition theorem “P ⇒ Hamiltonian” is falsified only by a graph that satisfies P yet is NOT Hamiltonian — not by a sparse Hamiltonian graph that fails to satisfy P. No such counterexample exists for (a), (b), or (c); each remains a correctly-stated, valid sufficient condition. This matches the exam’s own published final answer key for this question (UGC NET June 2015, Computer Science Paper 2), which records all three statements as correct.
Result: All three statements (a), (b), and (c) are correctly-stated theorems, so the correct choice is “(a), (b) and (c)”.