Principio de encasillamiento para demostrar un gráfico hamiltoniano

Question

Estoy tratando de averiguar si un gráfico puede ser asumido como hamiltoniano o no, o si es indeterminable con un mínimo de información:

A graph has 17 vertices and 129 edges.

Los grafos hamiltonianos se prueban mediante, siempre que los vértices sean mayores o iguales a 3 (que es este), entonces si la suma de los grados de dos vértices no adyacentes es mayor o igual a los vértices (17 en este caso), el grafo es hamiltoniano.

A mí me parece que esto es un tipo de prueba del principio de encasillamiento. Necesito determinar si pueden existir 2 vértices no adyacentes con grados que sumen 17 o más.

¿Alguien podría ayudarme a pensar en esto? He deducido que cada vértice debe ser al menos de grado 1 (si no el grafo estaría desconectado), y que al menos un vértice tendrá más de un grado debido al concepto de encasillamiento. A partir de ahí no sé cómo enfocarlo.

Gracias por cualquier ayuda.

Editar: ¿No dice el teorema de Dirac que los grados de los vértices deben ser TODOS mayores o iguales a n/2, en este caso, 8,5, o quizás 9? No lo había considerado antes, pero eso me sigue dejando con la misma pregunta, ¿cómo puedo demostrar (probablemente con palomita) que cada vértice tendrá al menos 9?

Answer 1

El teorema de Dirac dice que el grafo es hamiltoniano si cada vértice tiene grado al menos $9$ . Por lo tanto, supongamos que hay un vértice $v$ con grado $8$ o menos.

Si el resto $16$ vértices forman un gráfico completo, cada uno de ellos tiene grado $15$ , excepto por el extra $8$ vértices conectados a $v$ que tienen grado $16$ . Ese gráfico tiene el mayor número de aristas posible sin dejar de ser no-dirático. Entonces, el número de aristas es la mitad de la suma de los grados, o $\frac{1}{2} (8 + 15\cdot 8 + 16 \cdot 8) = 128$ bordes.

Answer 2

Para forzar un ciclo hamiltoniano en un grafo no dirigido en $n$ vértices requeriría al menos $ {{n-1}\choose 2} + 2 $ aristas, que es una más que el número de aristas de un gráfico completo en $(n-1)$ vértices más una arista que conecta ese gráfico con el $n$ vértice.

Para $n=17$ es decir $122$ Así que, a menos que haya una construcción mejor de un grafo no hamiltoniano muy denso, $129$ bordes son más que suficientes. $129$ es el número mínimo necesario para forzar la aplicabilidad del teorema de Dirac, pero es un requisito más fuerte.

Actualización. No existe una "mejor construcción". Que $ {{n-1}\choose 2} + 1 $ es el tamaño máximo de un grafo no hamiltoniano fue demostrado por Ore ( Recubrimientos de arcos de grafos ) en 1961 y la unicidad del grafo máximo fue demostrada por Bondy ( Variaciones sobre el tema hamiltoniano ) en 1972. Por lo tanto, $122$ Los bordes son necesarios y suficientes cuando $n=17$ .

Answer 3

El gráfico es $7$ aristas que faltan para ser completas, por lo que el grado mínimo es $16 - 7 = 9$ . De ahí que se pueda aplicar el teorema de Dirac.