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.
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
, se houver mais de dois vértices de grau ímpar então não existe em
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
possui um caminho euleriano
que percorre todas as arestas de
uma única vez. Os vértices
e
são os extremos de
, e os vértices
são os vértices internos.
Passo 3
Cada vez que o percurso
atinge um vértice interno
(com
), ele entra por uma aresta e sai por outra, usando duas incidências em
. Como
usa todas as arestas exatamente uma vez, todas as arestas incidentes em
aparecem em pares “uma de entrada, uma de saída”. Logo
é a soma de um número par de incidências, isto é,
é par para todo vértice interno.
Passo 4
Restam apenas os extremos
e
, 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
tivesse mais de dois vértices de grau ímpar, seria impossível construir tal caminho
, 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.