dav

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Sobre ciclos e caminhos hamiltonianos, é incorreto afirmar:

1. Quando removida uma aresta de um ciclo hamiltoniano sempre se obtém um caminho hamiltoniano
2. Não há ciclos hamiltonianos em grafos bipartidos com número ímpar de vértices
3. Se os vértices de início e fim de um caminho hamiltoniano forem adjacentes é possível obter um ciclo hamiltoniano
4. O numero de diferentes ciclos hamiltonianos num grafo não-direcionado completo com n vértices é  (n − 1)! / 2
5. NDA

Ideia original de: Daniel Vidal