Hay dos preguntas que básicamente preguntan lo mismo. Una está categorizada como una repetición, pero simplemente no siento que las respuestas de la otra sean válidas. Deja que $G$ sea un grafo de grado mínimo $k>1$. Demuestra que $G$ tiene un ciclo de longitud al menos $k+1$ Para la primera respuesta que recibió 9 votos positivos, no explica por qué cada vecino de un vértice está en el camino P. El camino no permite vértices repetidos, así que no veo explícitamente cómo uno puede viajar desde el nodo a todos sus vecinos y regresar sin pasar por el nodo en sí. Si viaja fuera de la imagen, digamos que va a otro nodo e intenta regresar, tampoco veo cómo puede hacerlo explícitamente. Cualquier ayuda es apreciada.
Respuesta
¿Demasiados anuncios?
scolja
Puntos
145
Probamos por inducción en $d$. Si $d = 1$ hay una arista, y esta es el camino necesario. Supongamos $d ≥ 2$, el resultado es cierto para $d < D$, y el grado mínimo de tu gráfica es $d$. Por la hipótesis de inducción $G$ tiene un camino $P$ de longitud al menos $d − 1$. Si la longitud de $P$ es al menos $D$, entonces hemos terminado. Así que supongamos que la longitud es $D − 1$ y la secuencia de vértices es $v_1, . . . , v_D$. El vértice $v_1$ tiene al menos $D$ vértices adyacentes, por lo que hay un vértice $w$ que es adyacente a $v_1$, pero no está en el camino $P$. Por lo tanto $w, v_1, . . . , v_D$ es un camino en $G$ con $D$ aristas.
Ahora probamos que si $D ≥ 2$, entonces $G$ tiene un ciclo de longitud de al menos $D + 1$. Sea $P = v_0, v_1, . . . , v_m$ un camino de longitud máxima en $G$. El argumento de la parte anterior muestra que $m ≥ D$, y que cada vértice $w_d$ adyacente a $v_0$ está en el camino $P$. Supongamos, empezando en $v_0$, que los vértices $w_d$ aparecen en el orden $w_1, . . . , w_L$. Entonces extendemos el camino $v_0, . . . , w_L$ a un ciclo agregando la arista $w_Lv_0$. El ciclo resultante tiene al menos $D + 1$ vértices, y por lo tanto tiene una longitud de al menos $D + 1$.
