Sea G un gráfico de grado mínimo k > 1. Demostrar que G tiene un ciclo de longitud al menos k+1

Question

Sea G un gráfico de grado mínimo k > 1. Demostrar que G tiene un ciclo de longitud al menos k+1

¿Cómo puedo mostrar esto? Entiendo que un ciclo es una secuencia de no-repitió vértices y el grado de un grafo es el número de vecinos del vértice.

Answer 1

Deje $P=v_0v_1 \dots v_l$ ser un camino más largo en $G$. $v_0$ tiene que tener otros vecinos por el grado de restricción. Todos los vecinos de $v_0$ tiene que ser en $P$, de lo contrario $P$ podría ser extendido. Por lo tanto, $v_0$ tiene al menos $k$ vecinos en $P$. Deje $j$ ser el índice máximo de un vecino de $v_0$. La instrucción anterior tenemos que $j \ge k$. Por lo tanto tenemos el ciclo de $v_0v_1 \dots v_jv_0$, que tiene una longitud de, al menos,$k+1$.

Answer 2

Esto puede ser resuelto a través de la bien-principio de orden. Vamos camino P ser el más largo camino en el grafo G que se inicia en el punto a, que tiene el grado más bajo de la gráfica. Si tiene Un grado mayor que 2, entonces se tendrá algunos vecinos de punto de W. Si W no estaba en P, entonces habría un vecino que no está en P, y luego P no sería el camino más largo, por lo menos Una del otro vecino está en el camino así, esto crea una contradicción. Como resultado, W tiene que ser en P, de lo contrario, tendríamos dijo contradicción, lo que significa que todos los de los vecinos están en P. Esto crea un ciclo, y desde un ciclo tiene una longitud de, al menos, |V(G)| + 1, este camino se han longitud de al menos k + 1.

Si hay un error con esto, me acabo de enterar de esto en clase hace una semana, así que estoy lejos de la perfección.