# How to show that complement a of regular graph is a Hamiltonian graph? [closed]

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?

## closed as off-topic by Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos SantosDec 10 '18 at 0:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.

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$$.