I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me.
Question: Let $G = (V,E)$ be an undirected $r$-regular graph (that is each vertex has a degree of $r$) for some $0 < r < n$, where $|V| = n > 1$. Prove that either $G$ or its complement $G^*$ has a hamiltonian path.
Now the reason it's asking for $G$ or $G^*$ is because if it's not a connected undirected graph then taking the complement will make it connected.
So lets assume that it's a connected $r$-regular graph. We start at a vertex $v$. From this vertex we can visit up to $r$ adjacent vertices. So we visit one of them, say $u$, and from there we have $r-1$ vertices to choose from because we do not want to go back to vertex $v$.
Now I am trying to formulate a proof by going from vertex to vertex until all vertices are visited exactly once (hamiltonian path). But I do not see how to formulate the proof. Somehow each new vertex I visit will always have an uninformed neighbour until I reach the final vertex on the path.
Am I on the right track?