Estaba leyendo "Teoría de grafos" por Diestel y trató de resolver un problema desde el capítulo 3 (de conectividad). Parece a primera vista fácil (y muy intuitiva) pero tengo que admitir que yo no puedo hacer ejercicio! Aquí está el problema: demostrar que cada $k$-conectado gráfico de orden al menos $2k$ contiene un ciclo de longitud al menos $2k$.
¿Alguien tiene una sugerencia?
Parece ser otra aplicación del Teorema de Dirac.
Primero supongamos por contradicción que la duración del ciclo más largo $C$$2k-1$. A continuación, consideremos el conjunto de vértices en $C$, que están conectados con los vértices fuera de $C$. Tiene cardinalidad, al menos,$k$. De lo contrario, mediante la eliminación de estos vértices, el gráfico de la izquierda está todavía conectado.
Luego, por el principio del palomar hay dos adyacentes verticies $A$$A'$$C$, que están conectados con los vértices fuera de $C$, dicen, $B$$B'$.
La situación al $B=B'$ automáticamente hace que un ciclo más largo. Al $B$ $B'$ son diferentes, borramos $C$, y obtener un grafo conexo. Nos conectamos $B$$B'$, utilizando todos los vértices fuera de $C$. Esto hace que la duración del ciclo.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
