Es bien sabido que la gráfica de Petersen no es hamiltoniana. Puedo demostrarlo mediante una distinción de casos, que no es demasiado larga - pero tampoco es muy elegante.
¿Existe un argumento sencillo (breve) para demostrar que el gráfico de Petersen no contiene un ciclo hamiltoniano?
Si se puede utilizar la simetría (como sugiere Jernej), el argumento del caso tiene mucho a su favor.
Hay una prueba que utiliza el entrelazado. Obsérvese que si $P$ tiene un ciclo de Hamilton, entonces su gráfica lineal $L(P)$ contiene una copia inducida de $C_{10}$ . El entrelazamiento de valores propios implica entonces que $\theta_r(C_{10}) \le \theta_r(L(P))$ . Pero $\theta_7(C_{10}) \approx -0.618$ y $\theta_7(L(P))=-1$ . [He olvidado a quién se debe este argumento. También hay una serie de variantes del mismo].
Supongamos que existe un ciclo Ham. Colorea los vértices a lo largo del ciclo alternativamente $5$ Rojo y $5$ Azul. Cada vértice tiene ahora al menos dos vecinos del color opuesto.
Pero a partir de dos vértices adyacentes del mismo color (deben existir en un grafo no bipartito), sólo hay una forma de completar un $2$ -con al menos dos vecinos del color opuesto a cada vértice. Resulta que $6$ los vértices reciben un color y $4$ obtener la otra -una contradicción.
Otro argumento fácil es utilizar el número cromático de las aristas, que es 4 para el grafo de Petersen. Si es hamiltoniano, entonces la eliminación del ciclo hamiltoniano deja un emparejamiento perfecto. En En este caso, 3 colores serían suficientes para colorear las aristas: 2 para el ciclo y 1 para la para el emparejamiento.
Motivado por la página de wikipedia Voy a añadir una respuesta a la pregunta por mí mismo. Sigue siendo una pequeña distinción de casos, pero es pequeña.
Sabemos que el grafo de Petersen es 3-regular y tiene una circunferencia de 5. Supongamos que tiene un ciclo hamiltoniano $H$ y dibujamos el gráfico de forma que el $H$ se dibuja como ciclo. Las aristas que no están en $H$ son acordes de $H$ . Si hubiera dos cuerdas que no se cruzan, entonces estas dos cuerdas forman parte de dos ciclos disjuntos 5. Pero en este caso las dos cuerdas y las dos aristas de $H$ no en los 5 ciclos forman un 4 ciclo. Por lo tanto, todas las cuerdas se cruzan por pares. La única posibilidad para esto se muestra en la segunda imagen. Claramente, tenemos un ciclo de 4. Por lo tanto, tenemos una contradicción.
Si tuviera un círculo hamiltoniano encontraríamos una coincidencia completa... si revisamos los 6 emparejamientos del grafico de petersen podemos ver que despues de quitar un emparejamiento completo de petersen el segundo grafico no es un circulo. esto demuestra que el grafico de petersen no tiene un circulo hamiltoniano.
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.
0 votos
La distinción de casos puede reducirse enormemente si se permite utilizar el hecho de que el gráfico de Petersen es transitivo a 3 arcos.
0 votos
Cómo podemos demostrar que es 3 arco transitivo. He demostrado que es suficiente para mostrar que tiene una órbita en 3 arcos. Pero no soy bueno en los argumentos de combinatoria así que me gustaría una pista.