Ore's Theorem - Proof

Proof

Suppose it were possible to construct a graph that fulfils condition (*) which is not Hamiltonian. According to this supposition, let G be a graph on n ≥ 3 vertices that satisfies property (*), is not Hamiltonian, and has the maximum possible number of edges among all n-vertex non-Hamiltonian graphs that satisfy property (*). Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path v₁v₂...v_n, for otherwise it would be possible to add edges to G without breaching property (*). Since G is not Hamiltonian, v₁ cannot be adjacent to v_n, for otherwise v₁v₂...v_n would be a Hamiltonian cycle. By property (*), deg v₁ + deg v_n ≥ n, and the pigeon hole principle implies that for some i in the range 2 ≤ i ≤ n − 1, v_i is adjacent to v₁ and v_{i − 1} is adjacent to v_n. But the cycle v₁v₂...v_{i − 1}v_nv_{n − 1}...v_i is then a Hamilton cycle. This contradiction yields the result.