Se G é um grafo simples conexo com pelo menos 2 vértices em que todos os vértices têm grau par então existe uma cadeia simples de comprimento máximo que contém todos os arcos
6. Se é possível percorrer todas as arestas de G uma e uma só vez, começando e terminando no mesmo vértice, então todos os vértices têm grau par.
...
6. Se e só se todos os vértices têm grau par então G é um grafo euleriano.
...
Prova por absurdo
...
Seja a referida cadeia de de comprimento máximo .
1ª Parte: A cadeia T é fechada (ciclo).
...
Se T é fechada, . Suponhamos por absurdo que é aberta (). Então:
º
Logo tem grau ímpar.
Mas como todos os vértices de têm grau par, teria de existir um arco a incidir em . Mas então teria comprimento o que é absurdo pois é maximal logo todas as cadeias têm comprimento .
Logo é cadeia fechada.
2ª Parte: A cadeia T contém todos os arcos de G.
...
Suponhamos por absurdo que não contém todos os arcos de e que existem arcos que não pertencem a . Como é conexo tem de existir um arco que ligue aos vértices dos arcos que não pertencem a T.
Mas então tem comprimento superior a o que é absurdo pois tem comprimento máximo.
Logo contem todos os arcos de .
Conclusão
...
Se todos os vértices de têm grau par então existe uma cadeia simples de comprimento máximo que contém todos os arcos (ciclo euleriano) e é um grafo euleriano.