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
    First of all: very nice. Seems like the key fact is somehow related to the distance between $x,y$ and the triangle. But could you also give a counter example for a $3$-regular graph?2012-04-20
  • 0
    Possibly, but how many times are you going to change the question?2012-04-20
  • 0
    Don't get me wrong, you are perfectly answering the main question. 3-regularity is in there since [Apr 3 at 17:48](http://math.stackexchange.com/posts/125159/revisions), because I still think the answer is **Yes** in this special case.2012-04-20
  • 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
    But I mean exactly $n$, not less! How do you reach $v_{n-1}$ without it?2012-03-27
  • 0
    If exactly $n$ steps is the requirement and you get to pick the start, you need to pick the start on the triangle. Otherwise you can't get to the neighboring vertices in the cycle. Imagine a hexagon, vertices $v_0, v_1, \ldots, v_5$ with $v_0, v_2$ added. You can't get from $v_4$ to $v_5$ in three steps. But you are essentially there. The idea of going around the triangle is the right one.2012-03-27
  • 0
    So you agree. What about the "only if" part?2012-03-27
  • 0
    @draks: I don't think only if is correct. Imagine a pentagon, vertices $v_0, v_1, \ldots, v_4$ with $v_0,v_2$ added and $v_5$ connected to $v_0$. I think you can get to any vertex in exactly three steps from $v_1$ but there is no Hamiltonian cycle.2012-03-27
  • 0
    But you need to reach every vertex from every other vertex. BTW: I didn't get your example. Can you give the adjacency matrix or a pic?2012-03-28
  • 0
    @draks: see above2012-03-28
  • 0
    So now that we cleared the *"anywhere from anywhere in n steps"* issue, what do you think?2012-04-03
  • 0
    @draks: I don't have an answer in that case. It seems reasonable, but I'm not sure2012-04-03
  • 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 $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.

  • 0
    First of all: Thanks. **"only if"**: Do you also have a counterexample if $G$ is planar? Sorry I forgot, to point that out. Mea culpa. **"if"**: Do you mean graph some like $C_7-C_3$? If not could you please provide a picture...?2012-04-03
  • 0
    @draks I'll need to think about planarity. You should edit the question also, so that others do not get confused.2012-04-03
  • 0
    I did. Thanks for your pictures and your effort (+1 as soon as I can ;-).2012-04-03
  • 0
    @draks To make a planar counterexample, remove the edge between b and c in the lolipop. There is still a route of exact length 3 between any two vertices.2012-04-03
  • 0
    @draks I now see that three connected is also required. Let me think (it now seems more plausible)2012-04-03
  • 0
    @draks The only if part remains false for 3 connected cubic planar graphs. Any of the graphs in figure 1 of [this paper](http://cs.anu.edu.au/~bdm/papers/c4cp.pdf) have paths of length 17 between any two distinct vertices (some edges may be traversed multiple times). This is tedious, but straghtforward to verify. The if direction, I suspect is true by some variation of your original proof, but I am not seeing it right now.2012-04-03
  • 0
    Very interesting paper; might take me while. (If you/others are also interested, this paper on ["Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs"](http://cs.anu.edu.au/~bdm/papers/HoltonCubicBipartite.pdf) might be interesting).2012-04-03
  • 0
    Now **I** don't see that it is straightforward to verify that the figure-1-graphs qualify as counterexamples.2012-04-03
  • 0
    @draks Oops, what looks like a triangle in the diagram isn't. Sorry. I'll see what I can dig up. I am certain that the only-if part is false. I suspect that the if part is true.2012-04-03
  • 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