Teoria dos Grafos → Hamiltoniano

Teorema de Dirac

Seja \(G\) um grafo simples com \(n \ge 3\) vértices. Se todo vértice satisfaz \( \ grau(v) \ge \frac{n}{2} \), então \(G\) possui um ciclo hamiltoniano.

\text{Se } \ grau(v) \ge \frac{n}{2} \text{ para todo } v \in V, \text{ então } G \text{ é hamiltoniano.}

Intuição: se cada vértice está conectado a pelo menos metade do grafo, há conectividade suficiente para “costurar” um ciclo passando por todos os vértices.

Importante: Essa é uma condição suficiente, não necessária. Um grafo pode ser hamiltoniano mesmo sem satisfazer essa desigualdade.

Teorema de Ore

Seja \(G\) um grafo simples com \(n \ge 3\) vértices. Se, para todo par de vértices não adjacentes \(u\) e \(v\), vale \( \ grau(u) + \ grau(v) \ge n \),
então \(G\) possui um ciclo hamiltoniano.

\begin{aligned} \text{Se } \ grau(u) + \ grau(v) \ge n &\text{ para todo par não adjacente } (u,v), \\ &\text{ então } G \text{ é hamiltoniano.} \end{aligned}

Intuição: mesmo que dois vértices não estejam ligados diretamente, a soma dos seus graus garante conectividade suficiente no restante do grafo.

O Teorema de Ore generaliza o de Dirac. Se a condição de Dirac é satisfeita, então a condição de Ore também é satisfeita.

Matemática Discretapara Engenheiros

Teorema de Dirac

Teorema de Ore