How to show that complement a of regular graph is a Hamiltonian graph?

Question

I have a regular graph G of degree k ≥ 1 (ie its every vertex is of degree k) with at least 2k+2 vertices. How do I show that complement of G is a Hamiltonian graph?

Answer 1

Indeed, let $n$ be the number of vertices of the graph. Since graph $G$ is $k$-regular, its complement $\overline{G}$ is $(n-1-k)$-regular. To apply Ore’s theorem it suffices to check that $2(n-1-k)\ge n$ which holds iff $n\ge 2k+2$.