If a graph of $2n$ vertices contains a Hamiltonian cycle, then can we reach every other vertex in $n$ steps?

Question

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!

Answer 1

The answer is no.

Question: Let $G$ be a 3-connected, hamiltonian, planar graph with $2n$ vertices and at least one triangle. Is it true that for all vertex pairs $x,y$, that there is a walk of exactly $n$ steps from $x$ to $y$?

The following graph and vertex pair is a counter example

It is clear that the graph is planar and has a triangle. It can be easily verified that the graph is 3-connected. To show that the graph is hamiltonian, I have highlighted a hamiltonian cycle here

Since the vertex has 16 vertices, we need to verify that there is no walk of length 8 from $x$ to $y$. Since $n$ is equal, we can not reach $y$ without using some of the four vertices on the right. Now it is easy to verify by hand, that there is no walk from $x$ to $y$ of length exactly 8.

Answer 2

Is the problem to reach any other vertex from a given starting point $v_0$ in $n$ steps? If so, why not ignore the triangle? The path is of length $2n$, so the farthest point is $n$ away along the path.

Added for the not only if part: See below. You can get anywhere in three steps from $v_1$ but not from $v_4$. It wasn't clear to me whether you have to get anywhere from one place in $n$ steps or anywhere from anywhere in $n$ steps.

Answer 3

Only if: Having a triangle and being able to travel between any two vertices in exactly $n$ steps does not imply a hamiltonian cycle. Consider the Lollipop graph $L_{5,1}$, any two points can be reached in exactly three steps, it obviously contains a triangle, and it does not contain a hamiltonian path. To see that every pair of distinct points can be reached in three steps, first consider two vertices in the $K_5$, there is a path of length 3 made by visiting two of the vertices of the $K_5$ different from the starting and ending vertices. Then consider the path from the vertex of degree 1 to a vertex on the $K_5$, go to the vertex of degree 6, then visit a vertex of the $K_5$ other than the degree 6 vertex or the ending vertex, and then finish.

I also do not like your proof of the 'if' direction. Consider a cycle of length 7 with a triangle attached. You cannot travel from the point opposite the triangle to a point adjacent to it in 4 steps. This may be simpler to visualize as a cycle of length 8 with two vertices distance two apart joined. The reason that your proof fails is that the triangle is too far away to be useful.

In the attached picture, you cannot travel from $a$ to $b$ in exactly four steps.