Let $G$ be a simple regular graph of odd degree, with $n\geq 4$ vertices. Show that $G$ or its complementary graph $\overline{G}$ is hamiltonian.
First, if we assume that $G$ is $r-$regular we obtain: Since $G$ is $r-$regular so if $r\geq n/2$ we have that $G$ is Hamiltonian. In the other hand we have that $\overline{G}$ is $(n-r-1)-$regular so if $n-r-1\geq n/2$ then $\overline{G}$ is hamiltonian.
I think that proof of this result is made by contradiction using Ore's Theorem. That is, to assume, absurdly, that $G$ and $\overline{G}$ are both non-hamiltonian. Then we have that $r<n/2$ and $n-r-1<n/2$. I'm not sure, just an idea.
Can anyone help me to prove this?
If $r\ge\frac{n}2$, then
$$\deg_Gu+\deg_Gv=2r\ge n$$
for every pair of vertices of $G$, so $G$ is Hamiltonian by Ore’s theorem.
Let $v$ be any vertex of $G$. There are $n-1$ other vertices, and $G$ is $r$-regular, there are $n-1-r$ vertices that are not adjacent to $v$ in $G$. These are precisely the vertices adjacent to $v$ in $\overline{G}$, so $\deg_{\overline{G}}v=n-1-r$, and $\overline{G}$ is $(n-1-r)$-regular.
Suppose now that $r<\frac{n}2$; then
$$n-1-r>n-1-\frac{n}2=\frac{n}2-1\,.$$
If $n$ is even, $\frac{n}2-1$ is an integer, so $n-1-r\ge\frac{n}2$, and $\overline{G}$ is Hamiltonian by Ore’s theorem.
If $n$ is odd, the smallest integer greater than $\frac{n}2-1$ is $\frac{n}2-\frac12=\frac{n-1}2$, so all that we can conclude is that $n-1-r\ge\frac{n-1}2$. If in fact $n-1-r\ge\frac{n+1}2$, we can apply Ore’s theorem to conclude that $\overline{G}$ is Hamiltonian, but if $n-1-r=\frac{n-1}2$, Ore’s theorem doesn’t apply. In this case, however, we can apply a theorem due to Nash-Williams to conclude that $\overline{G}$ is Hamiltonian. In fact, in this case both $G$ and $\overline{G}$ are $\frac{n-1}2$-regular, so both are Hamiltonian.