Um passeio euleriano é um passeio entre dois nós distintos de um (multi)grafo que percorre cada arco exatamente uma vez. Mostre que um (multi)grafo conexo contém um passeio euleriano se, e somente se, possui exatamente dois nós com grau ímpar.
Passo 1
O enunciado pede para mostrar que um (multi)grafo conexo
admite um passeio euleriano (isto é, um trail entre dois vértices distintos que percorre cada aresta exatamente uma vez) se, e somente se, possui exatamente dois vértices de grau ímpar. O conteúdo principal é a teoria de grafos envolvendo graus de vértices e as condições para existência de passeio ou circuito euleriano.
Passo 2
(Necessidade) Suponha que exista em
um passeio euleriano que começa em
e termina em
, com
. Em todo vértice interno do passeio, cada vez que entramos por uma aresta devemos sair por outra, contribuindo com
ao grau desse vértice. Já nos extremos
e
o passeio tem uma aresta a mais saindo de
(ou entrando em
) e uma aresta a mais chegando em
(ou saindo de
), de modo que
e
são ímpares. Logo, exatamente dois vértices têm grau ímpar.
Passo 3
(Suficiência) Agora suponha que
seja conexo e tenha exatamente dois vértices de grau ímpar, digamos
e
. Construa o grafo
adicionando em
uma aresta extra ligando
a
. Nesse novo grafo
todos os vértices passam a ter grau par, e
permanece conexo. Pelo teorema clássico de Euler, um grafo conexo com todos os vértices de grau par admite um circuito euleriano
. Removendo a aresta extra de
, obtemos em
um passeio que começa em
, termina em
e percorre cada aresta de
exatamente uma vez.
Resposta
Concluímos que um (multi)grafo conexo contém um passeio euleriano entre dois vértices distintos se, e somente se, possui exatamente dois vértices de grau ímpar.