Mi pregunta es igual que la anterior. Podríamos primero dejar que el conjunto S sea aquellos vértices de corte mínimo $S=\{x|x\in\kappa(G)\}$ . Entonces, podemos dividir S en algunos subconjuntos. En los subconjuntos, todos los elementos son adyacentes a algunos otros elementos. Sin embargo, todos los elementos no son adyacentes a diferentes subconjuntos. La longitud del camino más corto necesario para conectar dos subconjuntos es al menos dos. Creo que lo más importante es conectar elementos en subconjuntos iguales. Quiero afirmar que existe un camino que conecta todos los elementos con 2#(S). He descubierto que cada elemento en los mismos subconjuntos tiene al menos un grado de tres. De lo contrario, podríamos utilizar vértices de corte más pequeños para cortar el gráfico original. Pero, que sin duda no puede determinar un camino simple para conectarlos. Si cada vértice en los mismos subconjuntos tiene al menos un grado de cuatro, excepto los elementos que conectan otros subconjuntos, entonces podría demostrar esta cuestión. Sin embargo, me quedo atascado. ¿Puede alguien darme algunas pistas, gracias?
Respuesta
¿Demasiados anuncios?
Se parece a este lema:
"Si $G$ es un grafo conexo en $n$ vértices con grado mínimo $\delta(G)<\frac{n}{2}$ entonces existe un camino de longitud $2\delta(G)$ ."
La demostración del lema procede considerando un camino $P$ de longitud máxima y utiliza el hecho de que los vértices finales de $P$ tienen ambos grados al menos $\delta(G)$ . Es muy similar a la prueba del teorema de Dirac sobre los grafos hamiltonianos, tal vez lo hayas visto. La prueba completa está en la parte superior de la página 4: https://homepages.inf.ed.ac.uk/hguo/files/16.fall-adv.comb/Lecture_2_03.10.2016.pdf
Para tu problema, creo que aún puedes considerar un camino de longitud máxima y demostrar que sus vértices finales deben tener grado al menos $k(G)$ (¿por qué?), entonces la misma prueba debería funcionar.
