Os números de capítulos, seções, teoremas e exercícios se referem ao livro de Diestel, 2a edição.

10. Ciclos hamiltonianos

Um ciclo num grafo é hamiltoniano se for gerador, ou seja, se contiver todos os vértices do grafo. Um grafo é hamiltoniano se tem um ciclo hamiltoniano.
O problema de decidir se um dado grafo é hamiltoniano é completo em NP. Portanto, é pouco provável que exista um algoritmo polinomial para o problema.

10.1 Condições suficientes simples

Teorema 10.1.1 (Dirac): Se |G| ≥ 3 e delta(G) ≥ |G|/2 então G é hamiltoniano. (Compare com Proposição 1.3.1.)
Para todo número k existem grafos não hamiltonianos com delta(G) ≥ k. Grafos com alta conexidade têm ciclos longos (veja exercício 3.14). Grafos sem conjuntos independentes grandes têm ciclos longos (veja exercício 5.13).
Proposição 10.1.2 (Chvátal & Erdös): Se |G| ≥ 3 e kappa(G) ≥ alpha(G) então G é hamiltoniano.
Há uma relação íntima (pelo menos do ponto de vista histórico) entre ciclos hamiltonianos, planaridade, e coloração de faces. (Veja exercício 6.12 e seção 6.5.)
Teorema 10.1.3 (Tutte): Todo grafo 4-conexo planar é hamiltoniano.
(Mas o teorema não vale com 3 no lugar de 4.)

Exercícios:
1. Suponha que um grafo G tem um conjunto S de vértices que é maior que o número de componentes de G − S. Mostre que G não é hamiltoniano.
2. Um grafo G é k-tenaz (= k-tough) se comps(G − S) ≤ |S| / k para toda parte S de V(G). (Aqui, comps(G − S) é o número de componentes de comps(G − S).) Verifique na literatura o status da seguinte conjectura (Chvátal, 1971): Todo grafo 2-tenaz é hamiltoniano. Verifique na literatura a veracidade da seguinte conjectura: Existe k tal que todo grafo k-tenaz é hamiltoniano.
3. [10.4] Suponha que d(x) + d(y) ≥ |G| para todo par (x, y) de vértices não adjacentes. Mostre que G é hamiltoniano.
4. Veja o exercício 5.13.

Proposição (Chvátal): Se d(v₁) ≤ … ≤ d(v_n) e d(v_i) ≤ i implica em d(v_n–i) ≥ n − i para todo i < n/2, onde v₁, … , v_n são os vértices de G, então G é hamiltoniano.
Uma sequência numérica (a₁, … , a_n) é hamiltoniana se todo grafo com n vértices e sequência de graus termo-a-termo maior ou igual a (a₁, … , a_n) é hamiltoniano.
Teorema 10.2.1 (Chvátal): Uma sequência a₁ ≤ … ≤ a_n < n é hamiltoniana se e só se, para todo i < n/2, a_i ≤ i implica em a_n–i ≥ n − i.

Exercícios:
1. [10.6, fácil] Encontre um grafo hamiltoniano cuja sequência de graus não é hamiltoniana.
2. Se a sequência (a₁, … , a_n) é hamiltoniana então a₁ > 1. Analogamente, a₂ > 2.
3. [10.7] Suponha que, para todo i < |G|/2, o número de vértices de grau ≤ i é estritamente menor que i. Mostre que G é hamiltoniano. (Use o Teorema 10.2.1.)

Definição do grafo G^d: Dois vértices x e y de G são adjacentes em G^d se e só se dist_G(x, y) ≤ d.
Teorema 10.3.1 (Fleishner): Se G é 2-conexo então G² é hamiltoniano.
(O teorema de Fleishner é análogo ao seguinte fato: a duplicação de todas as arestas de um grafo arbitrário produz um grafo euleriano. A propósito, o problema chinês do carteiro (= chinese postman problem) consiste em encontrar o número mínimo de arestas cuja duplicação torna o grafo euleriano.)
Conjectura (Seymour): Para todo k, se |G| ≥ 3 e delta(G) ≥ |G| k / (k+1) então G tem um ciclo hamiltoniano H tal que H^k é subgrafo de G.

Exercícios:
1. [10.8] Exiba um grafo G tal que G² não é hamiltoniano.
2. [10.9, difícil] Se G é conexo então G³ é hamiltoniano.
3. [10.10] Suponha que x e y são dois vértices de um grafo 2-conexo G. Mostre G² tem um caminho hamiltoniano (ou seja, um caminho que contém todos os vértices do grafo) de x a y.
4. [10.11] Mostre que todo torneio tem um caminho hamiltoniano orientado.