Cykle w Grafie Dwudzielnym

[Nitr0Skay]

Powiedzmy, że mamy taki najprostszy graf dwudzielny
... h_K3,3.svg

"W grafie dwudzielnym każdy cykl ma parzystą długość."

Na powyższym obrazku łatwo jest zliczyć, że powyższe stwierdzenie jest prawdziwe. Tylko jak tego matematycznie dowieść ?

[gardner]

O to ,czy jest to najprostszy graf dwudzielny bym się spierał (zauważ ,że to graf dwudzielny pełny). Podpowiedź: jakbyś miał mi napisać co to jest graf dwudzielny to co byś nasmarował?

[Nitr0Skay]

Swoimi słowami to taki graf, który ma dwa różne zbiory wierzchołków i każdy z tych wierzchołków łączy się z każdym wierzchołkiem z drugiego zbioru, nie łącząc się przy tym z wierzchołkiem ze swojego zbioru.

[gardner]

No właśnie,a w cyklu musimy wrócić do wierzchołka początkowego. Da się to zrobić przechodząc nieparzystą ilość razy? No nie,nie da się. Najprościej to napisać tak: graf dwudzieln można podzielić na dwie klasy dwudzielności \(\displaystyle{ V_{1} i V_{2}}\) Startujemy więc z cyklem:
\(\displaystyle{ v_{0} \in V_{1}, v_{1} \in V_{2},...........,v_{n} \in V_{2}, v_{0} \in V_{1}}\) Już widzisz? Jaki wnioski można wyciagnąć?