La teoría de grafos pregunta

Question

Aquí es un ejercicio en el libro de Bondy/Murty que no soy muy capaz de entender.

Mostrar que cada gráfico tiene un vértice $x$ y una familia de $\left\lfloor\frac{1}{2}d(x)\right\rfloor$ ciclos cualquier dos de los cuales se encuentran solamente en el vértice $x$.

Answer 1

Yo tengo una solución sin necesidad de utilizar el principio del Palomar...

Tomar el camino más largo $P$ en el gráfico $v_1 - v_2 -... -v_k$ (con todos los vértices distintos). Considerar uno de los extremos, dice $v_1$. Todos sus vecinos deben pertenecer a $P$ (por maximality de $P$).

Deje $v_{i_1},v_{i_2},...,v_{i_d}$ ser sus vecinos : $2=i_1<i_2<...<i_d\leq k$$d=d(v_1)$.

Ahora usted tiene su $d'=\lfloor d/2 \rfloor$ ciclos, salas de reuniones sólo en $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$

Como es en el Bondy y Murty del libro, no está claro que se puede utilizar el principio del Palomar y en realidad no tengo idea de cómo se puede utilizar aquí.