Cadeias e ciclos eulerianos
Dado um grafo G
chama-se cadeia euleriana de G
a uma cadeia
simples
que passe por todas as
arestas de G. Analogamente, chama-se
ciclo euleriano de G a um
ciclo
que contenha todas as
arestas de G.
Teorema de Euler
Seja G um grafo conexo.
-
G admite uma ciclo euleriano
se e somente se todos os vértices de
G têm grau par.
-
G admite uma cadeia aberta euleriana
se e somente se G tem exactamente dois
vértices de grau ímpar. Neste caso todas as
cadeias eulerianas têm este par de
vértices de grau ímpar como extremidades.