1
$\begingroup$

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?

$\endgroup$

closed as off-topic by Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos Dec 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.

0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.