I've been stuck in this homewoork problem, and I've already asked my teacher and he told me that I have the idea by contradiction using Ore's Theorem and by watching $r$.
But I got some issues beacause for example. Assuming that $G$ is not Hamiltonian then for every non-adyacents vertexs $u$ and $v$ then $d(u) + d(v) < n$.
Notice that $d(u) = d(v)$.
But, for example when you have a $2-$regular Graph on $6$ vertexs then $d(u) + d(v) = 4$b
and $4 \geq 6$, not true. But this Graph still Hamiltonian.
So I'm stuck here.
I'm trying by cases when $|V(G)|$ is odd and when is even.
Any help?
Best Answer
Hint Since $G$ is $r$ regular, then it's complement is $n-1-r$ regular,
If neither $G$ or $\overline{G}$ is Hamiltonian, then by Ore Theorem $$r+r \leq n-1 \\ (n-1-r)+(n-1-r) \leq n-1$$
Deduce from here that $r=\frac{n-1}{2}$. Then $n$ needs to be odd, and hence, by Handshaking Lemma of the form $4k+1$.
This solves the problem unless $n=4k+1$ and $r=2k$.
The last case follows from this post