Solution

ID: past-exam-of-the-probability-statistics-and-options-ii-course-of-the-university-of-oxford/2011/r/r2/a/ii/solution

Take a complete graph on vertices and add a fifth vertex joined only to and . The minimum degree is two, which is less than . The only nonadjacent pairs are and , and each has degree sum . Thus Ore's condition holds even though the minimum-degree condition fails. For example,
is a Hamiltonian cycle in this graph.

New to topics? Read the docs here!