En teoría de grafos , el teorema de Grinberg es una condición necesaria para que un grafo plano contenga un ciclo hamiltoniano , en función de las longitudes de los ciclos de sus caras. Si un grafo no cumple esta condición, no es hamiltoniano. El resultado se ha utilizado ampliamente para demostrar que ciertos grafos planos construidos para tener propiedades adicionales no son hamiltonianos; por ejemplo, puede demostrar la no hamiltonicidad de algunos contraejemplos de la conjetura de Tait de que los grafos poliédricos cúbicos son hamiltonianos.
El teorema de Grinberg debe su nombre al matemático letón Emanuel Grinberg , quien lo demostró en 1968.
Un grafo plano es un grafo que se puede dibujar sin cruces en el plano euclidiano . Si se eliminan del plano los puntos que pertenecen a los vértices y aristas, los componentes conexos de los puntos restantes forman polígonos, llamados caras , incluyendo una cara no acotada que se extiende hasta el infinito. Una cara es un -gono si su límite está formado por un ciclo de vértices y aristas del dibujo del grafo. Un ciclo hamiltoniano en un grafo es un ciclo que pasa por cada vértice exactamente una vez. Sea un grafo plano finito con un ciclo hamiltoniano , con un dibujo plano fijo. Por el teorema de la curva de Jordan , separa el plano en el subconjunto dentro de y el subconjunto fuera de ; cada cara pertenece a uno de estos dos subconjuntos. Denote por y el número de caras -gonales del dibujo que están dentro y fuera de , respectivamente. Entonces el teorema de Grinberg establece que La demostración es una consecuencia fácil de la fórmula de Euler . [1] [2]
Como corolario de este teorema, si un grafo plano embebido tiene solo una cara cuyo número de lados no es 2 mod 3, y las caras restantes tienen todos números de lados que son 2 mod 3, entonces el grafo no es hamiltoniano. Para ver esto, considere una suma de la forma dada en el enunciado del teorema, para una partición arbitraria de las caras en dos subconjuntos, contados por los números y . Cada cara cuyo número de lados es 2 mod 3 contribuye con un múltiplo de tres a la suma, debido al factor en el término al que contribuye, mientras que la cara restante no lo hace. Por lo tanto, la suma no es un múltiplo de tres, y en particular no es cero. Dado que no hay forma de dividir las caras en dos subconjuntos que produzcan una suma que obedezca el teorema de Grinberg, no puede haber un ciclo hamiltoniano. [1] Por ejemplo, para el gráfico de la figura, todas las caras acotadas tienen 5 u 8 lados, pero la cara no acotada tiene 9 lados, por lo que satisface esta condición en cuanto a número de lados y no es hamiltoniana.
Grinberg utilizó su teorema para encontrar grafos poliédricos cúbicos no hamiltonianos con alta conectividad de aristas cíclicas. La conectividad de aristas cíclicas de un grafo es el menor número de aristas cuya eliminación deja un subgrafo con más de un componente cíclico. El grafo de Tutte de 46 vértices , y los grafos poliédricos cúbicos no hamiltonianos más pequeños derivados de él, tienen una conectividad de aristas cíclicas de tres. Grinberg utilizó su teorema para encontrar un grafo poliédrico cúbico no hamiltoniano con 44 vértices, 24 caras y una conectividad de aristas cíclicas de cuatro, y otro ejemplo (mostrado en la figura) con 46 vértices, 25 caras y una conectividad de aristas cíclicas de cinco, la máxima conectividad de aristas cíclicas posible para un grafo plano cúbico distinto de . En el ejemplo mostrado, todas las caras acotadas tienen cinco u ocho aristas, ambos números que son 2 módulo 3, pero la cara no acotada tiene nueve aristas, desiguales a 2 módulo 3. Por lo tanto, por el corolario del teorema de Grinberg, el gráfico no puede ser hamiltoniano. [1]
El teorema de Grinberg también se ha utilizado para encontrar grafos hipohamiltonianos planos , grafos que no son hamiltonianos pero que pueden volverse hamiltonianos eliminando cualquier vértice. La construcción nuevamente hace que todas las caras excepto una tengan un número de aristas congruente con 2 módulo 3. [3] Thomassen (1981) usa el teorema de una manera algo más complicada para encontrar un grafo hipohamiltoniano cúbico plano : el grafo que construye incluye una cara de 4 aristas adyacente a cuatro caras de 7 aristas, y todas las demás caras tienen cinco u ocho aristas. Para satisfacer el teorema de Grinberg, un ciclo hamiltoniano tendría que separar una de las caras de 4 o 7 aristas de las otras cuatro, lo que no es posible. [4]
También se puede aplicar para analizar los ciclos hamiltonianos de ciertos grafos no planares, como los grafos de Petersen generalizados , encontrando subgrafos planares grandes de estos grafos, usando el teorema de Grinberg para demostrar que estos subgrafos no son hamiltonianos y concluyendo que cualquier ciclo hamiltoniano debe incluir algunas de las aristas restantes que no son parte de estos subgrafos. [5]
Existen grafos no hamiltonianos planos en los que todas las caras tienen cinco u ocho lados. Para estos grafos, la fórmula de Grinberg tomada módulo tres siempre se cumple para cualquier partición de las caras en dos subconjuntos, lo que impide la aplicación de su teorema para demostrar la no hamiltonicidad en este caso. [6]
No es posible utilizar el teorema de Grinberg para encontrar contraejemplos a la conjetura de Barnette de que todo grafo poliédrico cúbico bipartito es hamiltoniano. Todo grafo poliédrico cúbico bipartito tiene una partición de las caras en dos subconjuntos que satisfacen el teorema de Grinberg, independientemente de si también tiene un ciclo hamiltoniano. [7]
