Probar que G contiene al menos un ciclo con bordes de $k+1$

Question

Que $k\geq 2$. Demostrar que si $G$ es $k$-regular, entonces $G$ contiene un ciclo con al menos $k+1$ bordes.

La forma en lo hizo fue para demostrar que el camino más largo en $G$ debe tener al menos $k$ bordes y que un camino deben ser una falta de un ciclo, y así el ciclo más largo debe contener al menos $k+1$ bordes. ¿Es correcta esta manera? ¿Hay otras maneras más directas de acercarse a este problema? ¡Gracias!

Answer 1

lo siento, veo que esto es una vieja pregunta, así que mi respuesta es, probablemente, atrasados... Creo que la respuesta que usted propone es, en esencia correcto, usted debe sólo asegúrese de que usted también cubrir el caso en que el camino más largo contiene más de $k$ bordes. La clave es observar que para un camino más largo $P=v_1v_2\ldots v_l$, el vértice $v_l$ debe ser adyacente a $k$ vértices contenidos en $P$, ya que el $G$ $k-$regular y $P$ es un camino más largo. Así que, si el camino es más largo que el de $k$ bordes, recoger la subruta que contiene sólo $v_l$ y los vértices adyacentes a él (contiene al menos $k+1$ vértices). Ahora esta subruta tiene como vértices $v_l$ y un vértice adyacente a $v_l$ (de otra manera, este vértice no sería parte de la subruta). La conexión de este vértice con $v_l$ completa un ciclo con al menos $k+1$ bordes.