If a graph G has no loops or parallel edges and has n ≥ 3 vertices, then G is Hamiltonian if

(i) deg(v) ≥ n/3 for each vertex v

(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge

(iii) |E(G)| ≥ (1/3)(n − 1)(n − 2) + 2

1. A(i) and (iii) only
2. B(ii) only
3. C(ii) and (iii) only
4. D(iii) only

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. (ii) only

Explanation

(ii) is Ore's theorem. Dirac's condition needs deg(v) ≥ n/2, not n/3, and the edge-count theorem needs ½(n − 1)(n − 2) + 2 edges, not ⅓. Only (ii) is sufficient.