Definição
Um caminho hamiltoniano é um caminho que visita todos os vértices de um grafo exatamente uma vez.
Um ciclo hamiltoniano é um caminho hamiltoniano que, além disso, retorna ao vértice inicial, formando um ciclo.
Resumo:
Caminho hamiltoniano = visita todos os vértices uma vez.
Ciclo hamiltoniano = caminho hamiltoniano + volta ao início.
Caminho hamiltoniano = visita todos os vértices uma vez.
Ciclo hamiltoniano = caminho hamiltoniano + volta ao início.
Exemplos
Abaixo, dois exemplos típicos: um grafo que tem ciclo hamiltoniano e outro que não tem.
Exemplo A — Tem ciclo hamiltoniano
Um ciclo possível: A → B → C → D → A.
Exemplo B — Não tem ciclo hamiltoniano
O vértice F tem grau 1, então não pode existir ciclo hamiltoniano.