¿Cómo demostrar que un gráfico no es hamiltoniano?

Question

Suponga que le dan un gráfico $G$ con las propiedades que $G$ es 3-regular, $v_G = 10$ donde $v_G$ es el número de vértices en $G$ y circunferencia $(G) \geq 5$ . ¿Cómo se puede saber que $G$ no es hamiltoniano?

Hasta ahora, he estado intentando averiguarlo mirando la gráfica de Petersen, que sé que no es hamiltoniana a través de un resultado en un libro que tengo. El gráfico de Petersen tiene $v_G = 10$ y circunferencia $(G) = 5$ pero no sé cómo se relaciona esto con ser no hamiltoniano.

Answer 1

Conozco un teorema que dice "Sea $G$ sea un grafo. Si existe un conjunto $S$ de vértices tales que $G-S$ tiene más de $|S|$ componentes, entonces $G$ no tiene ciclo hamiltoniano". Se puede demostrar por contradicción.

Supongo que con "hamiltoniano" te refieres a "ciclo hamiltoniano", ya que eso es lo que aprendimos en la escuela. Además, un componente es un conjunto de vértices sin vecinos fuera del conjunto.

Answer 2

Parece que el sólo grafo 3-regular con exactamente 10 vértices y circunferencia $\ge 5$ es el gráfico de Petersen. Así que el hecho de que todos tales grafos no son hamiltonianos es simplemente porque el grafo de Petersen resulta serlo.

Primero supongamos que la circunferencia es 5 exactamente: Empieza dibujando el ciclo de 5. Como el grafo es 3-regular, cada uno de los vértices del 5-ciclo debe tener un vecino adicional, y estos vecinos deben ser todos nuevos y distintos porque si no se violaría el requisito de circunferencia. Pero eso significa que ahora sabemos todos de los vértices, y la única forma de dar a cada uno de los nuevos vértices dos aristas más sin crear 4 ciclos es conectarlos exactamente como el grafo de Petersen.

Si la circunferencia es 6 o más, un argumento similar produce rápidamente una contradicción.