Graf w którym każdy wierzchołek ma parzysty stopień

[Milo_17]

Cześć.
Mam takie zadanie
Niech \(\displaystyle{ G=(V,E)}\) będzie grafem, w którym \(\displaystyle{ E \neq \emptyset}\) i w którym każdy wierzchołek ma parzysty stopień.
1)Rozważając nietrywialne składowe pokzać że G ma cykl.
2) Pokazać również że jeśli usuniemy z grafu krawędzie należące do tego cyklu to w nowym grafie każdy wierzchołek w dalszym ciągu ma parzysty stopień.
3)Wywnioskować, że w G istnieje zbiór cykli zawierający każdą krawędź z E dokładnie jeden raz.

Chciałbym poprosić kogoś o sprawdzenie mojej próby zrobienia tego zadania i może podzielenie się swoim pomysłem.

1)G ma nietrywialną składową z założenia niepustości E. Nazwijmy ją \(\displaystyle{ G'=(V',E')}\) gdzie \(\displaystyle{ V'=(v1,v2,...,vn)}\). Weźmy dowolny wierzchołek\(\displaystyle{ vi _{1}}\) gdzie \(\displaystyle{ i_{1} \in \left\{1,2,...,n \right\}}\). Wiemy że \(\displaystyle{ v1}\) ma stopień niezerowy a więc dobierzmy dowolny wierzchołek który jest jego sąsiadem i oznaczmy go \(\displaystyle{ v2}\). Ponieważ \(\displaystyle{ v2}\) ma stopień parzysty to istnieje inny od \(\displaystyle{ v1}\) wierzchołek któr również jest sąsiadem \(\displaystyle{ v2}\) i oznaczymy go \(\displaystyle{ v3}\). Będziemy powtarzać ten proces aż natrafimy na wierzchołek (na pewno tak się zdarzy ponieważ liczba wierzchołków jest skończona) \(\displaystyle{ vi_{k}}\) gdzie \(\displaystyle{ i_{k} \in \left\{1,2,...,n \right\}}\) który pojawił się już wcześniej w naszym ciągu \(\displaystyle{ vj \in (v1,v2,v3,...,v(k-1)) \wedge
vj=vk}\). Mamy cykl \(\displaystyle{ vjv(j+1)v(j+2)...v(k-1)vk}\).

2) Po usunięciu krawędzi należących do naszego cyklu suma stopni przy każdym wierzchołku który należy do naszego cyklu zmniejszy się o dwa, a więc ich parzystość nie ulegnie zmianie. (Nie umiem w sumie tego uzasadnić dlaczego akurat o dwa ale wydaje się dość oczywiste)

3)Oznaczmy cykl \(\displaystyle{ C_{1}}\) który w znaleźliśmy w naszym grafie \(\displaystyle{ G}\) i usuńmy go, a a nasz graf bez cyklu oznaczmy \(\displaystyle{ G'}\). Ponieważ suma stopni w \(\displaystyle{ G}\) jest dalej parzysta (wynika to bezpośrednio z 2)) to istnieje w nim cykl oznaczmy go \(\displaystyle{ C_{2}}\) i usuńmy go. Powtarzając ten proces usuwając kolejne cykle \(\displaystyle{ C_{i}}\) (liczba ich jest skończona ponieważ liczba krawędzi jest skończona) dojdziemy do momentu w którym otrzymamy graf pusty bez cykli. A zbiór \(\displaystyle{ \left\{C_{1},C_{2},...,C_{m} \right\}}\) będzie zbiorem cykli zawierających każdą krawędź dokładnie raz.


Najbardziej mi zależy na podpunkcie 1) i jego zgrabnym zapisaniu. Proszę o porady!

[arek1357]

Tak w skrócie do 1

Weźmy:

\(\displaystyle{ v_{0}}\) - dowolny wierzchołek grafu.
Twórzmy drogę D, dopóki D nie jest cyklem robimy:

niech.: \(\displaystyle{ v_{i}}\)

będzie sąsiadem .: \(\displaystyle{ v_{i-1}}\)

wybór jest możliwy ponieważ:

\(\displaystyle{ deg(v_{i-1}) \ge 2}\)

jeśli \(\displaystyle{ v_{i}}\) - jest wierzchołkiem należącym do drogi.: \(\displaystyle{ v_{i−1}, ..., v_{0}}\)
to droga D zawiera cykl.

jeśli nie to:

\(\displaystyle{ v_{i}}\)

dołączamy do drogi.: \(\displaystyle{ v_{i},v_{i−1}, ..., v_{0}}\)

takie pierdu, pierdu...