Form a new graph H by adding a new vertex w to G that is adjacent to every vertex of G.
Then in H, every two non-adjacent vertices x, y in G satisfy,
deg x in H+ deg y in H= deg x in G +1 + deg y in G + 1≥ n − 1+ 2 = n + 1 = V(H ) , and so all the edges
between vertices of G belong to the closure of H. Thus, the closure of H is complete and it
follows that H must have a Hamiltonian cycle, call it C. So it follows that C - w is a
Hamiltonian path in G