Graf spójny,dwudzielny i regularny

[gardner]

Jeśli graf \(\displaystyle{ G}\) jest regularny, spójny, dwudzielny i ma co najmniej \(\displaystyle{ 3}\) wierzchołki to \(\displaystyle{ G}\) jest dwuspójny.

Jedyne do czego doszedłem to to, że jeśli mamy graf regularny i dwudzielny to na pewno ma on skojarzenie doskonałe. To jednak nie implikuje tego,że jest dwuspójny.

Dwuspójność z kolei oznacza,że dla każdych dwóch różnych wierzchołków \(\displaystyle{ u,v}\) istnieje cykl w grafie \(\displaystyle{ G}\) taki,że te wierzchołki należą do tego cyklu.
Jakieś wskazówki? Pierwszą rzeczą jest to,że nie wiem czy tylko tymi przejściami sobie nie komplikuje życia.

[Zordon]

Załóż nie wprost, że istnieje krawędź rozspajająca...

[gardner]

Załóżmy,że istnieje krawędź rozspajająca. Graf \(\displaystyle{ G}\) jest dwudzielny więc (\(\displaystyle{ V=V_{1} \cup V_{2})}\) jeden z jej końców musi należeć do \(\displaystyle{ V_{1}}\)a drugi do \(\displaystyle{ V_{2}}\).
Mamy więc dopiero \(\displaystyle{ 2}\)wierzchołki (w założeniu co najmniej \(\displaystyle{ 3}\)). Musi więc istnieć co najmniej \(\displaystyle{ 1}\)sąsiad wierzchołka należącego do \(\displaystyle{ V_{1}}\) lub \(\displaystyle{ V_{2}}\). Dodajmy więc wierzchołek do wybranej dowolnie klasy wierzchołków. To powoduje,że graf nie jest regularny więc należy dodać do już dodanego kolejny wierzchołek. Musi być on połączony z już istniejącymi. Mamy więc cykl,co przeczy temu,że istnieje krawędź rozspajająca. Proszę kogoś o sprawdzenie czy tok rozumowania właściwy,o formalizm się pomartwię później.

[Zordon]

Nie jest właściwy.
Rozważ jeden z podgrafów powstałych po rozspojeniu.
Jest również dwudzielny. Rozważ obie strony dwudzielności i sumę stopni wierzchołków tamże.