Defina o que é um grafo Hamiltoniano.
Passo 1
O enunciado pede para definirmos o que é um grafo Hamiltoniano: estamos em Teoria dos Grafos e precisamos entender os conceitos de caminho Hamiltoniano e ciclo Hamiltoniano para chegar à definição.
Passo 2
Um caminho Hamiltoniano em um grafo é uma sequência de vértices na qual cada vértice de $V$ aparece exatamente uma vez e há arestas ligando vértice a vértice consecutivo nessa sequência. Ou seja, é um passeio que visita todos os vértices sem repetir nenhum.
Passo 3
Um ciclo Hamiltoniano é um caminho Hamiltoniano que volta ao vértice de partida por uma aresta, fechando um circuito. Assim, ele visita cada vértice de $V$ exatamente uma vez e retorna ao início, formando um ciclo simples que passa por todos os vértices.
Passo 4
Dado isso, dizemos que um grafo $G = (V, E)$ é Hamiltoniano se existir pelo menos um ciclo Hamiltoniano em $G$. Em outras palavras, o grafo deve permitir um circuito que passe por todos os vértices exatamente uma vez.
Resposta
Um grafo
é Hamiltoniano se existir em
um ciclo Hamiltoniano, ou seja, um percurso fechado que visita cada vértice de
exatamente uma vez antes de retornar ao vértice inicial.