Teorema de Ore

O Teorema de Ore é um resultado provado em 1960 pelo matemático norueguês Øystein Ore relacionado à Teoria dos grafos. Ele fornece uma condição suficiente para um grafo para ser Hamiltoniano, essencialmente, afirmando que um grafo com "quantidade de arestas suficiente" deve conter um ciclo de Hamilton. Especificamente, a teoria considera a soma dos graus dos pares de vértices não adjacentes: se cada um destes pares tem uma soma que, pelo menos, é equivalente ao número total de vértices no grafo, então o mesmo é Hamiltoniano.

Gráfico exemplificando o Teorema de Ore

Definição formal

Seja G um grafo simples e finito com n ≥ 3 vértices. Denotaremos por deg v o grau do vértice v em G i.e. o número de arestas incidentes em G a partir de v. Então, o Teorema de Ore mostra que se :deg v + deg w ≥ n para todo par de vértices v distintos não-adjacentes e wde G (*) então G é hamiltoniano.

Prova

A prova se resume a demonstrar que todo grafo G não hamiltoniano não obedece a condição (*). Suponha G um grafo com n ≥ 3 vértices não-hamiltoniano, e seja H formado a partir de G adicionando arestas de forma a não criar um ciclo hamiltoniano, até que não seja possível adicionar mais arestas. Sejam x e y dois vértices não-adjacentes de H quaisquer. Então, adicionando a aresta xy em H vai criar ao menos um novo ciclo hamiltoniano, e as outras arestas irão formar um caminho hamiltoniano v ₁ v ₂ ... v _n em H com x = v ₁ e y = v _n. Para cada i no intervalo 2 ≤ i ≤ n, considere as duas arestas possíveis em H de v ₁ a v _i e de v _{i - 1} a v _n. Ao menos uma dessas duas arestas estará presente em H, caso contrário o ciclo v ₁ v ₂ ... v _i-1v _nv _n-1 ... v _i será um ciclo hamiltoniano. Assim, o total de arestas incidentes em v ₁ ou v _n será igual ao número de escolhas de i, cujo valor é n - 1. Portanto, H não pode obedecer à proposição (*), o que requer que o número total de arestas (deg v ₁ + deg v ₁) seja maior ou igual a n. Assim, os graus dos vértices em G são iguais aos graus de H, e segue que G também não obedece a propriedade (*).

Referências

• Bondy, J. A. (1971), «Pancyclic graphs I», Journal of Combinatorial Theory, Series B, 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5 .
• Meyniel, M. (1973), «Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté», Journal of Combinatorial Theory, Series B (em French), 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9  !CS1 manut: Língua não reconhecida (link).
• Ore, Ø. (1960), «Note on Hamilton circuits», American Mathematical Monthly, 67 (1): 55, JSTOR 2308928, doi:10.2307/2308928 .
• Palmer, E. M. (1997), «The hidden algorithm of Ore's theorem on Hamiltonian cycles», Computers & Mathematics with Applications, 34 (11): 113–119, MR 1486890, doi:10.1016/S0898-1221(97)00225-3 .
• Woodall, D. R. (1972), «Sufficient conditions for circuits in graphs», Proceedings of the London Mathematical Society, Third Series, 24: 739–755, MR 0318000, doi:10.1112/plms/s3-24.4.739 .