El teorema de Ore es un resultado de la teoría de grafos , probado en 1960 por el matemático noruego Oistin Ore . El teorema proporciona una condición suficiente para que un gráfico sea hamiltoniano , y establece esencialmente que un gráfico con "un número suficientemente grande de aristas" debe contener un ciclo hamiltoniano . En particular, el teorema considera las sumas de grados de pares de vértices no adyacentes: si cada par suma al menos el número total de vértices en un gráfico, entonces el gráfico es hamiltoniano.
Sea G un grafo (finito y simple) con n ≥ 3 vértices. Denote por grado v el grado de v en G , es decir, el número de aristas que inciden en v . El teorema de Ore establece que si
grado v + grado w ≥ n para cualquier par de vértices no adyacentes v y w del grafo G , (*)entonces G es hamiltoniano .
La afirmación es equivalente a decir que cualquier gráfico G no hamiltoniano viola la condición (*). Sea G un grafo no hamiltoniano con n ≥ 3 vértices. Deje que el gráfico H se forme a partir de G agregando aristas, una por una, que no formen un ciclo hamiltoniano, mientras que es posible agregar tales aristas. Considere dos vértices no adyacentes x e y del gráfico H . Agregar un borde xy a H crea al menos un ciclo hamiltoniano, y los bordes que no sean xy en ese ciclo deben formar un camino hamiltoniano v 1 v 2 ... v n en H con x = v 1 e y = v n . Para cada índice i en el rango 2 ≤ i ≤ n , considere dos posibles aristas en H de v 1 a v i y de v i − 1 a v n . A lo sumo una de estas aristas puede estar presente en H , porque de lo contrario el ciclo v 1 v 2 ... v i − 1 v n v n − 1 ... v i v 1 sería hamiltoniano. Por lo tanto, el número total de aristas incidentes en v 1 o v n no excede el número de posibles i , que es igual a n − 1 . Por lo tanto, H no satisface la condición (*), que requiere que el número total de aristas ( grado v 1 + grado v n ) sea mayor o igual que n . Dado que los grados de los vértices de G no exceden los grados en H , entonces G tampoco satisface el requisito (*).
Palmer [1] describe el siguiente algoritmo simple para construir un ciclo hamiltoniano en un gráfico que satisface la condición de Ore.
Cada paso aumenta el número de pares adyacentes consecutivos en uno o dos pares (dependiendo de si v j y v j + 1 ya son adyacentes), de modo que el ciclo externo del algoritmo puede ejecutarse un máximo de n veces antes de romperse, donde n es el número de vértices de este gráfico. Por razones similares a las dadas en la demostración del teorema, el índice j debe existir, de lo contrario los vértices no adyacentes vi y vi + 1 tienen un grado total demasiado pequeño. La búsqueda de i y j con la subsiguiente inversión de parte del bucle se puede realizar en tiempo O( n ). Por lo tanto, el tiempo total de ejecución del algoritmo es O( n 2 ).
El teorema de Ore es una generalización del teorema de Dirac , que establece que si cada vértice tiene un grado de al menos n /2 , entonces el gráfico es hamiltoniano. Es claro que si el grafo satisface la condición de Dirac, la suma de los grados de los pares de vértices será al menos n .
A su vez, el teorema de Ore se ha generalizado al teorema de Bondi-Chwatala . Puede definir un cierre de gráfico agregando, para cada par de vértices no adyacentes con un grado de suma de al menos n , un borde que conecta estos vértices. Si un grafo satisface la condición del teorema de Ore, su cierre es un grafo completo . El teorema de Bondy-Chwatal establece que un grafo es hamiltoniano si y solo si su cierre es un grafo hamiltoniano. Dado que el gráfico completo es hamiltoniano, el teorema de Ore se sigue inmediatamente de este teorema como corolario.
Woodall [2] encontró una versión del teorema de Ore que se aplica a grafos dirigidos . Supongamos que un dígrafo G tiene la propiedad de que para cualesquiera dos vértices u y v existe un arco de u a v , o el grado de salida de u más el grado de entrada de v es al menos tanto como el número de vértices en g _ Entonces, por el teorema de Woodall, G contiene un ciclo hamiltoniano orientado. El teorema de Ore se puede derivar del teorema de Woodall reemplazando cada borde con un par de arcos dirigidos. Un teorema de Meinel estrechamente relacionado [3] establece que un dígrafo de n -vértices fuertemente conectado con la propiedad de que para cualquier vértice no adyacente u y v el número total de aristas incidentes en u o v es al menos 2n − 1 debe ser hamiltoniano.
El teorema de Ore se puede reforzar dando un requisito más estricto que ser hamiltoniano, como consecuencia de la condición de grados de vértice en el teorema. En particular, cualquier gráfico que satisfaga las condiciones del teorema de Ore es un gráfico bipartito completo regular o un gráfico pancíclico [4] .