Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Interesting question. –  Saeed Apr 9 '12 at 23:13
add comment

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
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? –  draks ... Apr 20 '12 at 7:15
    
Possibly, but how many times are you going to change the question? –  utdiscant Apr 20 '12 at 10:11
    
Don't get me wrong, you are perfectly answering the main question. 3-regularity is in there since Apr 3 at 17:48, because I still think the answer is Yes in this special case. –  draks ... Apr 20 '12 at 10:19
    
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. –  utdiscant Apr 20 '12 at 11:07
add comment

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

share|improve this answer
    
But I mean exactly $n$, not less! How do you reach $v_{n-1}$ without it? –  draks ... Mar 27 '12 at 21:01
    
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. –  Ross Millikan Mar 27 '12 at 21:17
    
So you agree. What about the "only if" part? –  draks ... Mar 27 '12 at 21:46
    
@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. –  Ross Millikan Mar 27 '12 at 22:34
    
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? –  draks ... Mar 28 '12 at 10:34
show 4 more comments

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.

share|improve this answer
    
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...? –  draks ... Apr 3 '12 at 17:44
    
@draks I'll need to think about planarity. You should edit the question also, so that others do not get confused. –  deinst Apr 3 '12 at 17:58
    
I did. Thanks for your pictures and your effort (+1 as soon as I can ;-). –  draks ... Apr 3 '12 at 17:59
    
@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. –  deinst Apr 3 '12 at 18:05
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. –  deinst Apr 9 '12 at 22:52
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.