Condições Necessárias
As condições abaixo são necessárias para um grafo possuir um ciclo hamiltoniano. Ou seja: se alguma delas falhar, então não existe ciclo hamiltoniano.
- Sem vértice folha: todo vértice deve ter grau \( \text{grau}(v) \ge 2 \).
- Grafo conexo: é preciso conseguir alcançar qualquer vértice a partir de qualquer outro.
- Sem “vértice de corte” forçado: se remover um vértice e o grafo desconecta, esse vértice seria um gargalo difícil de contornar num ciclo.
Importante: “necessária” não quer dizer “suficiente”.
Mesmo se todas as condições acima forem verdadeiras, ainda pode não existir ciclo hamiltoniano.
Exemplos
Aqui vão dois contraexemplos rápidos que quebram condições necessárias e, por isso, não podem ter ciclo hamiltoniano.
Exemplo A — Vértice com grau 1
O vértice F tem grau 1, então não pode existir
ciclo hamiltoniano.
Exemplo B — Grafo desconexo
O grafo tem duas componentes. Como não é conexo, não pode existir
ciclo hamiltoniano.