Wykazać, że graf G jest eulerowski.

[andrzejek12]

Witam,
Mam problem z tego typu zadaniem:

Wykazać, że graf G = (V, E) jest eulerowski wtedy i tylko wtedy, gdy
zbiór jego krawędzi można podzieli¢ na cykle. (Chodzi o podział w
sensie matematycznym, czyli dzielimy zbiór E na rozłączne niepuste
zbiory E1, . . . , Ek takie, że suma = E Każdy ze zbiorów Ei ma być zbiorem krawędzi pewnego cyklu w grae G.)


Niby mniej więcej wiem o co chodzi, ale jak to ładnie wykazać? Bardzo proszę o Waszą pomoc

[Jytug]

Wynikanie w prawo jest raczej jasne - jeśli graf ma cykl Eulera, to łatwo można podzielić zbiór jego krawędzi na jeden cykl.

W lewo z kolei możemy skorzystać z twierdzenia Eulera. Jeżeli podzieliliśmy zbiór krawędzi na podzbiory będące cyklami (dajmy na to \(\displaystyle{ E_1, E_2 \dots E_k}\)), to każdy wierzchołek może być incydentny z jaką liczbą krawędzi z każdego spośród \(\displaystyle{ E_i}\)?

[norwimaj]

Implikacja w lewo nie przechodzi bez założenia spójności grafu.