El teorema de Ore es un resultado de la teoría de grafos demostrado en 1960 por el matemático noruego Øystein Ore . Da una condición suficiente para que un gráfico sea hamiltoniano , estableciendo esencialmente que un gráfico con suficientes aristas debe contener un ciclo de Hamilton . Específicamente, el teorema considera la suma de los grados de pares de vértices no adyacentes : si cada par tiene una suma que al menos iguala el número total de vértices en el gráfico, entonces el gráfico es hamiltoniano.
Sea G un gráfico (finito y simple) con n ≥ 3 vértices. Denotamos por grados v el grado de un vértice v en G , es decir, el número de aristas incidentes en G a v . Entonces, el teorema de Ore establece que si
entonces G es hamiltoniano .
Es equivalente a demostrar que todo gráfico no hamiltoniano G no obedece a la condición (∗) . En consecuencia, sea G un gráfico en n ≥ 3 vértices que no sea hamiltoniano, y deje que H se forme a partir de G agregando aristas una a la vez que no crean un ciclo hamiltoniano, hasta que no se puedan agregar más aristas. Sean x e y dos vértices cualesquiera no adyacentes en H . Entonces, agregar la arista xy a H crearía al menos un nuevo ciclo hamiltoniano, y las aristas distintas de xy en dicho ciclo deben formar una trayectoria hamiltoniana 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 las dos posibles aristas en H desde v 1 hasta v i y desde v i − 1 hasta v n . Como máximo una de estas dos 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 sería un ciclo hamiltoniano. Por lo tanto, el número total de aristas incidentes en v 1 o v n es como máximo igual al número de opciones de i , que es n − 1 . Por lo tanto, H no obedece a la propiedad (∗) , que requiere que este número total de aristas ( deg v 1 + deg v n ) sea mayor o igual a n . Dado que los grados de los vértices en G son como máximo iguales a los grados en H , se deduce que G tampoco obedece a la propiedad (∗) .
Palmer (1997) describe el siguiente algoritmo simple para construir un ciclo hamiltoniano en un gráfico que cumpla la condición de Ore.
Cada paso aumenta el número de pares consecutivos en el ciclo que son adyacentes en el gráfico, en uno o dos pares (dependiendo de si v j y v j + 1 ya son adyacentes), por lo que el bucle externo solo puede ocurrir como máximo n veces . antes de que termine el algoritmo, donde n es el número de vértices en el gráfico dado. Mediante un argumento similar al de la prueba del teorema, el índice j deseado debe existir, o de lo contrario los vértices no adyacentes vi y vi + 1 tendrían un grado total demasiado pequeño . Encontrar i y j y revertir parte del ciclo se puede lograr en el tiempo O ( n ). Por lo tanto, el tiempo total del algoritmo es O ( n 2 ), lo que coincide con el número de aristas en el gráfico de entrada.
El teorema de Ore es una generalización del teorema de Dirac de que, cuando cada vértice tiene un grado al menos n /2 , la gráfica es hamiltoniana. Porque, si un gráfico cumple la condición de Dirac, entonces claramente cada par de vértices tiene grados que suman al menos n .
A su vez el teorema de Ore es generalizado por el teorema de Bondy-Chvátal . Se puede definir una operación de cierre en un gráfico en el que, siempre que dos vértices no adyacentes tengan grados que sumen al menos n , se agrega un borde que los conecta; si una gráfica cumple las condiciones del teorema de Ore, su cierre es una gráfica completa . El teorema de Bondy-Chvátal establece que una gráfica es hamiltoniana si y sólo si su cierre es hamiltoniano; dado que la gráfica completa es hamiltoniana, el teorema de Ore es una consecuencia inmediata.
Woodall (1972) 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, por cada dos vértices u y v , hay una arista de u a v o el grado exterior de u más el grado interior de v es igual o excede el número de vértices en G. Entonces, según el teorema de Woodall, G contiene un ciclo hamiltoniano dirigido. El teorema de Ore se puede obtener de Woodall reemplazando cada arista en un gráfico no dirigido dado por un par de aristas dirigidas. Un teorema estrechamente relacionado de Meyniel (1973) establece que un n -vértice dígrafo fuertemente conectado con la propiedad de que, por cada dos vértices no adyacentes u y v , el número total de aristas incidentes en u o v es al menos 2 n − 1 debe ser hamiltoniano.
El teorema de Ore también puede reforzarse para dar una conclusión más sólida que la hamiltonicidad como consecuencia de la condición de grado del teorema. Específicamente, cada gráfico que satisface las condiciones del teorema de Ore es un gráfico bipartito completo regular o es pancíclico (Bondy 1971).