Todo camino k-conectado tiene un ciclo que contiene cualquier conjunto de k de los vértices.

Question

Se han planteado varias preguntas sobre este problema. Aquí está el que tiene las respuestas más detalladas . El problema es demostrar que un grafo k-conectado $G$ tiene un ciclo que contiene un conjunto arbitrario $x_1,x_2...x_k$ de los vértices.

La prueba consiste en considerar un ciclo máximo C que contenga el mayor número posible de $x_i$ . Si C no las incluye todas, digamos que algunas $x_m$ no está en C, entonces elige k puntos finales en el ciclo de manera que seccionen el ciclo C para tener una sección que no incluya ninguno de los $x_i$ . Por el teorema de Menger, podemos encontrar caminos disjuntos de vértices desde $x_m$ a cada uno de estos puntos finales, y ranurar el $x_m$ en la sección que no contiene ninguna otra de las $x_i$ . Todo esto parece muy bien ....

Sin embargo, no estoy del todo convencido. Supongamos que las rutas a cualquier punto final que se pueda elegir para una sección que no contenga ningún $x_i$ no son vértices disjuntos del resto del ciclo C. El teorema de Menger sólo nos da que los caminos de $x_m$ a los k puntos finales de C son disjuntos, ¡y no que cada camino sea también disjunto con el resto de los vértices de C! Me imagino que tal vez sea imposible encajar el vértice como se requiere, sin trocear el ciclo C de manera que nunca se tenga un ciclo que contenga todos los $x_i$ de inmediato.

Answer 1

No hay que apegarse a dónde están los puntos finales en $C$ son, ya que cualquier configuración de esos puntos finales puede hacer que las cosas funcionen.

Supongamos que tiene un ciclo $C$ que contiene $x_1, \dots, x_{m-1}$ pero no $x_m$ .

Digamos que eliges vértices $a_1, a_2, \dots, a_k$ en $C$ y, a continuación, encontrar vértice-disjuntos $x_m,a_i$ -sendas para $i=1, \dots, k$ . Si resulta que el camino de $x_m$ à $a_i$ en realidad visita primero otro vértice $b_i$ de $C$ Entonces, simplemente olvídese de la $b_i$ -a- $a_i$ segmento del camino, y sólo toma el segmento $x_m$ à $b_i$ . Ahora todavía tienes $k$ caminos de vértice disjuntos de $x_m$ à $C$ pero el $i^{\text{th}}$ uno es más corto.

O dicho de otro modo: podemos argumentar, por el teorema de Menger o por el lema del abanico de Dirac, que existe al menos una colección de $k$ trayectorias de vértices disjuntos que comienzan en $x_m$ con puntos finales en algún lugar de $C$ . Escoge el conjunto de caminos con la menor longitud total. Entonces ninguno de los caminos visita $C$ antes de llegar a su punto final - de lo contrario, se podría truncar dicha ruta para hacerla aún más corta.

Ahora el argumento que citas funciona sin problemas.

Reetiquetar los puntos finales de estas rutas como $c_1, c_2, \dots, c_k$ para que este sea el orden en que aparecen en el ciclo $C$ . Estos $k$ puntos finales romper $C$ en $k$ y uno de los segmentos (por ejemplo, de $c_{i-1}$ à $c_i$ ) no contiene nada de $x_1, \dots, x_{m-1}$ (porque eso es como máximo $k-1$ vértices). Reemplazar el segmento de $c_{i-1}$ à $c_i$ por el camino de $c_{i-1}$ à $x_m$ y el camino desde $x_m$ à $c_i$ y has encontrado un ciclo que contiene todos los $x_1, x_2, \dots, x_m$ .