Diante do apresentado sobre o circuito hamiltoniano, compreenda as afirmativas a seguir: I. Um graf...

Alternativa A - I e II, apenas.

Introdução

Circuitos e caminhos hamiltonianos referem-se à visitação de vértices em um grafo. Um caminho hamiltoniano visita cada vértice exatamente uma vez, enquanto um circuito hamiltoniano faz o mesmo e retorna ao vértice de origem.

Desenvolvimento

1. Grafos Completos (Kₙ): Em um grafo onde todos os nós estão conectados entre si, sempre haverá um ciclo que percorre todos os pontos, desde que haja pelo menos 3 vértices (n ≥ 3).
2. Relação Circuito-Caminho: Se você encontrou um circuito (um anel fechado que passa por todos os pontos), basta remover a última aresta que fecha o ciclo para obter um caminho (uma linha que passa por todos os pontos).

Análise

• I (Correta): Um grafo completo Kₙ para n ≥ 3 sempre possui circuitos hamiltonianos.
• II (Correta): A existência de um circuito implica logicamente a existência de um caminho (o circuito é um caso especial de caminho fechado).
• III (Incorreta): Ser conexo é condição necessária, mas não suficiente. Um grafo em formato de "estrela" ou uma linha simples (caminho) pode ser conexo e não possuir um circuito hamiltoniano.

Conclusão

Apenas as afirmações I e II são propriedades universais garantidas pela teoria dos grafos.

Alternativa A.