Problem: Given a graph $G,$ with $2n$ vertices and at least one triangle. Is it possible to show that you can reach every other vertex in $n$ steps if $G$ contains a Hamilton cycle (HC)?
EDIT: Sorry, I forgot to mention, that $G$ is planar and 3-connected. A complete proof for $3$-regular graphs would also be accepted/rewarded.
Does the following work as proof?
Choose a starting vertex $v_0$ and a direction.
- If you walk along the HC you'll reach a vertex $v_{n-1}$ with maximal distance from $v_0$ in $n$ steps.
- You'll reach $v_{n-2}$ by doing a round in the triangle and
- $v_{n-3}$ by stepping backwards at the last step.
- By combining these moves, you'll reach half of all $v_k$.
- By choosing the other direction at the beginning you'll reach the other half.
- $v_0$ is free to choose.
Showing or disproving the "only if"-part would also be nice!