5
$\begingroup$

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!

  • 1
    Interesting question.2012-04-09

3 Answers 3

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

enter image description here

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

enter image description 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.

  • 0
    I will certainly try to construct a new counter example for the 3-regular case, but my intuition is that it has to be a rather large counter example.2012-04-20
4

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.

enter image description here

  • 0
    @draks: No problem2012-04-03
4

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. Lolipop <span class=K_{5,1}">

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. A cycle with a triangle

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

  • 1
    @draks I still have not answered it, though. Keep your reputation. When I have time I'll try to find a counter example. If you find one, please add an answer to your own question.2012-04-09