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.

Here is an exercise from the book by Bondy/Murty that I am not quite able to understand.

Show that every simple graph has a vertex $x$ and a family of $\left\lfloor\frac{1}{2}d(x)\right\rfloor$ cycles any two of which meet only in the vertex $x$.

share|improve this question
    
What is $d(x)$? –  copper.hat Mar 25 '13 at 7:41
    
It's the degree. I was confused before too but it actually makes sense –  muzzlator Mar 25 '13 at 7:41
1  
Yeah, me neither. It's easy to get that many edge-disjoint cycles, but I'm having trouble seeing how to get vertex-disjoint cycles (which I think is what is being asked for). –  Greg Martin Mar 25 '13 at 19:39
3  
@GregMartin: It's not necessarily the vertex of minimal degree. Let $K_5$ be the complete graph on $5$ vertices. Now consider two copies of $K_5$, and let $v_1$ and $v_2$ be vertices of the first and second copy, respectively. Add a new vertex $v$ and edges $(v,v_1)$ and $(v,v_2)$. Then $v$ has minimum degree (2) but no cycle goes through $v$. –  Pedro Milet Mar 26 '13 at 13:44
1  
@PedroMilet Thank you for the nice counterexample. –  Greg Martin Mar 26 '13 at 16:06

1 Answer 1

up vote 8 down vote accepted

I have a solution without using the Pigeonhole principle...

Take the longest path $P$ in your graph $v_1 - v_2 -... -v_k$ (with all the vertices distinct). Consider one of the endpoints, says $v_1$. All its neighbours must belong to $P$ (by maximality of $P$).

Let $v_{i_1},v_{i_2},...,v_{i_d}$ be its neighbours : $2=i_1<i_2<...<i_d\leq k$ and $d=d(v_1)$.

Now you have your $d'=\lfloor d/2 \rfloor$ cycles, meeting only in $x=v_1$:

  • $v_1 -v_{i_1} - ... - v_{i_2} -v_1$

  • $v_1 -v_{i_3} - ... - v_{i_4} -v_1$

  • ...

  • $v_1 - v_{i_{2d'-1}} - ... - v_{i_{2d'}} - v_1$

As it is in the Bondy and Murty's book, it is not clear that you can use the Pigeonhole principle and actually I have no idea on how you can use it here.

share|improve this answer
    
You are right, the hint about the pigeonhole principle was referring to another exercise... how embarrassing... –  hannahh Mar 26 '13 at 14:29
    
I am a bit confused. What is $v_1$? is it a terminal point of $P$? –  hannahh Mar 26 '13 at 14:44
    
Yes it is one of the endpoint of P –  Aline Parreau Mar 26 '13 at 14:45
    
I don't see how we can guarantee that $d(v_1)>1$. –  hannahh Mar 26 '13 at 14:46
1  
If not, then $v_1$ satisfies $\lfloor d(v_1) /2 \rfloor =0$ and there is no cycle containing $v_1$, hence $x=v_1$ is a solution. –  Aline Parreau Mar 26 '13 at 14:47

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.