Consider a Hamiltonian Graph G with loops or parallel edges and with |V(G)| = n ≥ 3. Then which of the following is true?
Show answerHide answer
Correct answer: (D) All of the above
Explanation
By Dirac's theorem, deg(v) ≥ n/2 for every vertex; by Ore's theorem, deg(v) + deg(w) ≥ n for every pair of non-adjacent vertices v and w; and a graph with |E(G)| ≥ (1/2)(n – 1)(n – 2) + 2 edges is Hamiltonian. So all of the above.