Prove o seguinte teorema de Euler.
Teorema 2.12 Se um grafo tem mais de dois vértices de grau impar, ele não possui um caminho euleriano.
Dica: Tente uma demonstração por contradição, e modele o seu argumento a partir da demonstração do Teorema 2.8.

Passo 1

O enunciado pede para provar que, em um grafo G, se houver mais de dois vértices de grau ímpar então não existe em G nenhum caminho euleriano (isto é, nenhum caminho que percorra todas as arestas exatamente uma vez). O conteúdo é teoria de grafos, usando argumento de paridade de incidências de arestas em um percurso.

Passo 2

Suponha, por contradição, que G possui um caminho euleriano
P = v0,e1,v1,e2,dots,em,vm
que percorre todas as arestas de G uma única vez. Os vértices v0 e vm são os extremos de P, e os vértices v1,v2,dots,vm-1 são os vértices internos.

Passo 3

Cada vez que o percurso P atinge um vértice interno vk (com 1<= k<= m-1), ele entra por uma aresta e sai por outra, usando duas incidências em vk. Como P usa todas as arestas exatamente uma vez, todas as arestas incidentes em vk aparecem em pares “uma de entrada, uma de saída”. Logo
deg(vk)
é a soma de um número par de incidências, isto é, deg(vk) é par para todo vértice interno.

Passo 4

Restam apenas os extremos v0 e vm, que podem ter grau ímpar (pois em cada um deles o percurso ou começa sem “aresta de entrada” ou termina sem “aresta de saída”). Concluímos que num caminho euleriano há no máximo dois vértices de grau ímpar: os dois extremos. Se G tivesse mais de dois vértices de grau ímpar, seria impossível construir tal caminho P, contradizendo nossa hipótese.

Resposta

Como mostramos que um caminho euleriano só admite até dois vértices de grau ímpar, segue-se imediatamente que um grafo com mais de dois vértices de grau ímpar não pode ter caminho euleriano.

Exercícios de Livros Relacionados