Tengo una tarea para mi clase de Combinatoria y Grafos que no sé cómo terminar.
La tarea: Sea G un grafo simple de 14 vértices, con 4 vértices de grado 5 y 10 vértices de grado 7. Demuestra que G es hamiltoniano.
Hemos repasado los teoremas de Dirac y Ore, pero no estoy seguro de cómo utilizarlos (al menos al principio de la demostración), y también el teorema de Chvátal-Erdős, que parece más apropiado para empezar.
Hasta aquí he llegado: Sabemos que el número de aristas de este grafo es 45 (es decir, 4*5 + 10*7 dividido por dos, ya que contamos cada arista dos veces por grados), y el $K_1$$ _4 $ has 91 edges (($ 14,2$) - número de combinación), por lo que todavía podríamos añadir de alguna manera 91-45 = 46 aristas. Ahora, a partir de una variación del teorema C-E, sé que:
G es hamiltoniano $\iff G=(V,E_+)$ es hamiltoniano, donde E+ es E más la arista entre dos vértices no adyacentes cuya suma de grados es mayor o igual a n. Sabiendo que puedo añadir 46 aristas, puedo llegar al punto en que sé que dos vértices de 7-deg no están conectados - simplemente no hay suficientes vértices entre ellos. Así que puedo añadir una arista, y lo que quería demostrar es que puedo añadir las aristas de manera que habrá entonces dos vértices de al menos 9 grados por cada vértice de 5 grados, y así podría conectarlos de la misma manera que lo hice con los vértices de 7 grados, hasta el punto en que cada vértice de 5 grados tendría grado 7, después de lo cual podría utilizar el teorema de Dirac para demostrar que G es hamiltoniano. Sin embargo, este no parece ser el buen camino, o al menos no estoy del todo convencido de ello.
¿Podría alguien comentar si este es el buen camino a seguir, o mejor aún, indicarme la dirección correcta para la prueba? ¡Gracias!
