# Graph theory question

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$.

-
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
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
@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 M. Mar 26 '13 at 13:44
@PedroMilet Thank you for the nice counterexample. –  Greg Martin Mar 26 '13 at 16:06

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.

-
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
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