En teoría de grafos , el teorema de Grinberg es una condición necesaria para que un gráfico plano contenga un ciclo hamiltoniano , basándose en las longitudes de sus ciclos faciales. Si una gráfica no cumple esta condición, no es hamiltoniana. El resultado se ha utilizado ampliamente para demostrar que ciertos gráficos 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 gráficos poliédricos cúbicos son hamiltonianos.
El teorema de Grinberg lleva el nombre del matemático letón Emanuel Grinberg , quien lo demostró en 1968.
Una gráfica plana es una gráfica que se puede dibujar sin cruces en el plano euclidiano . Si los puntos que pertenecen a los vértices y aristas se eliminan del plano, los componentes conectados de los puntos restantes forman polígonos, llamados caras , incluida una cara ilimitada que se extiende hasta el infinito. Una cara es un -gón si su límite está formado por un ciclo de vértices y aristas del dibujo del gráfico. Un ciclo hamiltoniano en un gráfico es un ciclo que pasa por cada vértice exactamente una vez. Sea un gráfico plano finito con ciclo hamiltoniano , con dibujo plano fijo. Por el teorema de la curva de Jordan , separa el plano en el subconjunto interior y el subconjunto exterior ; cada cara pertenece a uno de estos dos subconjuntos. Denota 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 una gráfica plana incrustada tiene solo una cara cuyo número de lados no es 2 mod 3, y todas las caras restantes tienen números de lados que son 2 mod 3, entonces la gráfica no es hamiltoniana. 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 números y . Cada cara cuyo número de lados es 2 mod 3 aporta un múltiplo de tres a la suma, por el factor del término al que contribuye, mientras que la cara restante no. Por tanto, la suma no es múltiplo de tres y, en particular, no es cero. Como no hay forma de dividir las caras en dos subconjuntos que produzcan una suma que obedezca al 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 el número de lados y no es hamiltoniana.
Grinberg usó su teorema para encontrar gráficos poliédricos cúbicos no hamiltonianos con alta conectividad de bordes cíclicos. La conectividad de aristas cíclicas de un gráfico es el número más pequeño de aristas cuya eliminación deja un subgrafo con más de un componente cíclico. El gráfico Tutte de 46 vértices y los gráficos poliédricos cúbicos no hamiltonianos más pequeños derivados de él tienen conectividad de aristas cíclica tres. Grinberg usó su teorema para encontrar un gráfico poliédrico cúbico no hamiltoniano con 44 vértices, 24 caras y conectividad de aristas cíclicas cuatro, y otro ejemplo (que se muestra en la figura) con 46 vértices, 25 caras y conectividad de aristas cíclicas cinco, la máxima posible conectividad de borde cíclico para un gráfico plano cúbico distinto de . En el ejemplo mostrado, todas las caras acotadas tienen cinco u ocho aristas, las cuales son números 2 mod 3, pero la cara no acotada tiene nueve aristas, distintas a 2 mod 3. Por lo tanto, según el corolario del teorema de Grinberg , la gráfica no puede ser hamiltoniana. [1]
El teorema de Grinberg también se ha utilizado para encontrar gráficas hipohamiltonianas planas , gráficas que no son hamiltonianas pero que pueden hacerse hamiltonianas eliminando cualquier vértice único. La construcción nuevamente hace que todas las caras menos una tengan un número de aristas congruentes con 2 mod 3. [3] Thomassen (1981) usa el teorema de una manera algo más complicada para encontrar una gráfica hipohamiltoniana cúbica plana : la gráfica que construye incluye una 4 -cara de arista 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 cual no es posible. [4]
También se puede aplicar para analizar los ciclos hamiltonianos de ciertos gráficos no planos, como los gráficos de Petersen generalizados , encontrando grandes subgrafos planos de estos gráficos, usando el teorema de Grinberg para demostrar que estos subgrafos no son hamiltonianos y concluyendo que cualquier hamiltoniano El ciclo debe incluir algunos de los bordes restantes que no forman parte de estos subgrafos. [5]
Existen gráficos planos no hamiltonianos en los que todas las caras tienen cinco u ocho lados. Para estos gráficos, la fórmula de Grinberg tomada en módulo tres siempre se satisface con 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 gráfico poliédrico bipartito cúbico es hamiltoniano. Todo gráfico poliédrico bipartito cúbico 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]
