Qual das alternativas abaixo descreve corretamente o critério de existência de um caminho de Euler em um grafo conexo?
Resposta correta: C) O grafo deve ter zero ou dois vértices de grau ímpar.
Se houver 0 vértices ímpares, o caminho de Euler é um circuito; se houver 2, ele começa em um e termina no outro.
Considere o grafo da Figura 7.6a (matriz de adjacência mostrada no exemplo). Qual é o valor da variável total ao final da segunda iteração do laço enquanto no algoritmo CaminhoDeEuler?
Resposta correta: C) 2
Nas duas primeiras linhas da matriz, os graus são 3 (ímpar) e 3 (ímpar), portanto total passa a valer 2.
Qual das afirmações abaixo sobre circuitos hamiltonianos é falsa?
Resposta correta: B) Se um grafo tem exatamente dois vértices de grau ímpar, ele necessariamente tem um circuito hamiltoniano.
Essa condição refere‑se a caminhos de Euler, não a circuitos hamiltonianos.
Considere um grafo simples G com 12 vértices onde cada vértice tem grau 5. Qual é a resposta correta sobre a existência de caminhos de Euler e circuitos hamiltonianos?
Resposta correta: B) G tem circuito hamiltoniano, mas não tem caminho de Euler.
Todos os vértices têm grau ímpar (5), logo há 12 vértices ímpares > 2 → nenhum caminho de Euler. Como grau ≥ n/2 (5 ≥ 6?) não satisfaz Dirac, mas ainda assim grafos regulares de grau 5 em 12 vértices costumam ser hamiltonianos; a alternativa mais segura é B.