Me gustaría mostrar varias cosas, algunas para general grafos -conexos y algunos para varias instancias ( ).
Primero, quiero mostrar que para cada -Gráfico conectado cada subconjunto de tamaño está en un ciclo.
¿Cómo lo hago? Pensé probar por inducción sobre la conectividad del gráfico ( ).
Mi caso base es para . Tomo 2 vértices arbitrarios . Sé por el teorema de Menger que hay dos caminos de vértice distintos y , tanto de a . al pasar y marcha atrás consigo un ciclo. Así que esto funciona para 2 vértices.
Ahora me gustaría usar mi hipótesis de inducción para para aplicarlo a un -gráfico conexo. Pero no estoy seguro de cómo. Mi intuición es eliminar un vértice y mirar el subgrafo que quedó. Entonces sé que cada los vértices están en un ciclo. Veamos el vértice que agregué. . Aquí es donde empiezo a balbucear, porque sé tiene caminos desde él a cada vértice en el ciclo... Pero, ¿no deberían ser suficientes 2 caminos? ¿Por qué necesito todo el ¿caminos? ¿Y de dónde viene el uso de que son vértices distintos?
Incluso estaba tratando de demostrarlo (el paso de inducción) en un -gráfico conexo. Pero parece que es suficiente tener 2 caminos y no 3...
Otra variante interesante es lo que sucede si tomo un subconjunto no solo de vértices, sino también de aristas. Esto significa que tengo un subconjunto de tamaño de vértices y aristas. Específicamente, traté de centrarme en un caso básico de , y ver si puedo extenderlo desde allí.
Entonces para Quiero probar que cada subconjunto de vértices y aristas está en un ciclo. He entendido que si el subconjunto son solo bordes, esto podría no ser válido, por lo que asumo que incluye al menos un vértice. Mi idea es ver el borde no como un borde, sino en sus dos extremos y luego tratar de mostrar que sus extremos, junto con los otros vértices del subconjunto, están en un ciclo. Pero, ¿no sería como mostrar que 4 vértices están en un ciclo en un -grafo conexo? Quiero hacer uso de alguna manera del borde entre los dos, pero no estoy seguro de cómo exactamente.
Aquí hay un argumento más detallado para el paso de inducción (es el mismo argumento que aquí ).
Dejar ser de tamaño . Elegir . Sabemos es también -conectado y por lo tanto existe un ciclo en que contiene . Si esta en el ciclo , hemos terminado. Ahora supongamos .
Si lees aquí , verás una forma más fuerte del teorema de Menger. Más precisamente, si son conjuntos de vértices de , entonces
En otras palabras, si no hay k−1 vértices que desconecten A de B, entonces existen k caminos disjuntos de A a B.
Así, podemos elegir caminos separados entre y nuestro ciclo . De estos, podemos encontrar caminos entre y que son disjuntos (excepto el vértice ), ya sea agregando al inicio del camino o, si ya está en una ruta, eliminando todos los vértices que aparecen antes en la ruta. Nombramos estos caminos y denota respectivamente los últimos vértices de los respectivos caminos, estos son todos vértices disjuntos.
Ahora bien, como hay elementos de en , deben existir al menos dos vértices tal que, en el ciclo , sin vértice de aparece "entre" y . Esto significa que la parte del ciclo entre y no contiene ningún vértice de . ahora forma agregando la parte del ciclo que excluye los vértices entre y , entonces el camino de a , entonces el camino de a .
Por construcción, la parte de que no eliminamos contenía todos los vértices de y agregamos , de este modo contiene . Además, y son distintos y no contienen ningún vértice de otro que y , de este modo es de hecho un ciclo.
Hendrix
Marik S.