Por que os graus importam?
A chave dos grafos Eulerianos está no grau de cada vértice. Lembre-se que o grau de um vértice é o número de arestas incidentes a ele.
Em um percurso Euleriano, toda vez que chegamos a um vértice por uma aresta, normalmente precisamos de outra aresta para sair dele. Isso cria naturalmente pares de arestas: uma para entrar, outra para sair.
Por causa desse pareamento, a maioria dos vértices em um percurso Euleriano deve ter grau par. Se um vértice tem grau ímpar, sobra uma aresta sem par, o que significa que esse vértice só pode servir como uma extremidade especial do percurso.
Essa observação simples já é suficiente para caracterizar quando caminhos e ciclos Eulerianos existem. Em vez de procurar cegamente por todos os caminhos possíveis, podemos inspecionar os graus primeiro.
Ciclo Euleriano vs. Caminho Euleriano
Existem duas noções muito próximas:
Um ciclo Euleriano é um percurso fechado que utiliza todas as arestas exatamente uma vez e retorna ao vértice inicial.
Um caminho Euleriano é um percurso que utiliza todas as arestas exatamente uma vez, mas pode começar e terminar em vértices diferentes.
A diferença estrutural aparece diretamente na paridade dos graus: um ciclo não possui extremidades especiais, enquanto um caminho possui exatamente duas.
Portanto, um ciclo Euleriano exige que todos os vértices relevantes tenham grau par, enquanto um caminho Euleriano permite exatamente dois vértices de grau ímpar.
Teorema de caracterização
Seja G um grafo conexo, desconsiderando vértices isolados. Então:
Ciclo Euleriano: G possui um ciclo Euleriano se, e somente se, todo vértice tem grau par.
Caminho Euleriano: G possui um caminho Euleriano se, e somente se, exatamente zero ou dois vértices têm grau ímpar.
O caso de zero vértices ímpares corresponde a um ciclo Euleriano, pois o percurso começa e termina no mesmo vértice. O caso de dois vértices ímpares corresponde a um caminho Euleriano aberto, que começa em um vértice ímpar e termina no outro.
Se um grafo possui mais de dois vértices de grau ímpar, então não existe percurso Euleriano.
Por que a conectividade é necessária?
As condições de grau não são suficientes sozinhas. O grafo também deve ser conexo, ignorando vértices isolados.
O motivo é simples: um percurso Euleriano deve cobrir todas as arestas em um único trajeto. Se o grafo tiver arestas em componentes desconectados, nenhum percurso único consegue alcançar todas elas.
Vértices isolados não importam, pois não possuem arestas a serem percorridas. Problemas Eulerianos dizem respeito a cobrir arestas, não apenas visitar vértices.
Portanto, a condição completa é: paridade correta dos graus + conectividade da parte não isolada.
Exemplos
Considere três casos típicos:
Caso 1: todos os vértices têm grau par. Então o grafo admite um ciclo Euleriano.
Caso 2: exatamente dois vértices têm grau ímpar. Então o grafo admite um caminho Euleriano, mas não um ciclo.
Caso 3: quatro ou mais vértices têm grau ímpar. Então não existe caminho Euleriano.
Esses casos geralmente podem ser identificados apenas por inspeção, o que torna problemas Eulerianos muito mais tratáveis do que problemas Hamiltonianos.
Conexão com Königsberg
No grafo de Königsberg, mais de dois vértices possuem grau ímpar. Portanto, o grafo não pode ter um caminho Euleriano.
Euler não precisou testar todos os caminhos possíveis. Assim que o padrão de graus foi identificado, a resposta seguiu diretamente da estrutura.
Este foi um dos primeiros grandes exemplos na matemática de substituir intuição geométrica por raciocínio estrutural.