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 G 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 G um passeio euleriano que começa em u e termina em v, com u\neq v. Em todo vértice interno do passeio, cada vez que entramos por uma aresta devemos sair por outra, contribuindo com 2 ao grau desse vértice. Já nos extremos u e v o passeio tem uma aresta a mais saindo de u (ou entrando em u) e uma aresta a mais chegando em v (ou saindo de v), de modo que \deg(u) e \deg(v) são ímpares. Logo, exatamente dois vértices têm grau ímpar.

Passo 3

(Suficiência) Agora suponha que G seja conexo e tenha exatamente dois vértices de grau ímpar, digamos s e t. Construa o grafo G' adicionando em G uma aresta extra ligando s a t. Nesse novo grafo G' todos os vértices passam a ter grau par, e G' permanece conexo. Pelo teorema clássico de Euler, um grafo conexo com todos os vértices de grau par admite um circuito euleriano C. Removendo a aresta extra de C, obtemos em G um passeio que começa em s, termina em t e percorre cada aresta de G 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.

Exercícios de Livros Relacionados