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

Solution 1:

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.