If $G$ is $2r$-regular ($r \geq1$), $|V(G)|=4r+1$ and there is a simple cycle of length $4r$ then $G$ is Hamiltonian

Question

How could I start my proof? I have drawn $G$ for $r=2$ but still have no clue how to kick off.

Answer 1

So you have a cycle of length $4r$, and $4r+1$ vertices in all, so there's just one vertex, call it $v$, not in your $4r$-cycle. Now $v$ has degree $2r$, so it's adjacent to half the vertices in your cycle. If it's adjacent to vertices $x$ and $y$ that are adjacent to each other in your cycle, you're laughing; start at $x$, go around your cycle in the direction away from $y$, until you get to $y$, then go to $v$, then go to $x$, and you're done. So we suppose that no two of the vertices in the cycle that are adjacent to $v$ in the graph are adjacent to each other in the cycle.

Let's label the vertices around the cycle as $1,2,\dots,4r$, and let's take $v$ as adjacent to precisely the ones with even labels. Then vertex 2 can't be adjacent to all $2r$ odd-labeled vertices, since it has degree $2r$ and is adjacent to $v$. So it's not adjacent to the odd-labeled vertex $x$. Then $x$ must be adjacent to some odd-labeled vertex $y$, since it has degree $2r$ and it's not adjacent to $v$ and it's not adjacent to all the even-labelled vertices. We may assume $x<y$. Go from $v$ to $x+1$ to $x+2$ to ... to $y$ to $x$ to $x-1$ to $x-2$ to ... to $y+1$ (including going from 1 to $4r$) to $w$ (oops, make that $v$), and you're done.