Proposição: Condição necessária para a existência de ciclos eulerianos
Se G admite um ciclo euleriano então todos os vértices de G têm grau par.
Seja G um grafo e c uma cadeia elementar
em G. Designemos por Gc o grafo parcial de G
gerado pelas arestas em c.
Se c é um ciclo então todos os vértices de Gc
têm grau par.
Se c é uma cadeia aberta então as extremidades de
c têm grau ímpar em Gc.
Todos os restantes vértices de Gc
têm grau par.
A animação em baixo mostra uma sequência de cadeias elementares c,
começando na cadeia vazia e
terminando num ciclo euleriano. A cada instante podem ver-se
as valências (graus) dos vários vértices em Gc.
Para correr a animação coloque o rato sobre a figura.
A animação pára sempre que afaste o rato da figura.
Proposição: Condição suficiente
para a existência de ciclos eulerianos
Seja G um grafo conexo com todos os seus vértices de grau par.
Então G admite um ciclo euleriano.
Lema 1:
Seja G um grafo com todos os seus vértices de grau par.
Então
G admite ciclos.
O grafo parcial H de G que se obtem
removendo todas as arestas de um ciclo tem também
todos os seus vértices de grau par.
Lema 2:
Seja G um grafo com todos os seus vértices de grau par.
Então o conjunto das arestas de G pode ser decomposto numa união finita
de ciclos disjuntos.
