graf dwudzielny, spójność

[aGabi94]

Wykaż,że jeśli \(\displaystyle{ \delta(G) \geq \frac{|X|+1}{2}}\) to G jest spójny. Czy implikacja jest również prawdziwa jeśli założymy \(\displaystyle{ \delta(G) \geq \frac{|X|}{2}}\) .
Wiem, że graf jest spójny, jeżeli istnieje ścieżka między dowolnymi wierzchołkami , mamy tu graf dwudzielny, więc musi istnieć ścieżka między np. x1 i x2, y1,y2 lub x i y, ale nie wiem jak formalnie zapisać ten dowód.

[Kartezjusz]

Możesz objaśnić oznaczenia?

[aGabi94]

\(\displaystyle{ G(X,Y,E)}\) -graf dwudzielny
\(\displaystyle{ \delta(G)}\) - stopień minimalny wierzchołka
\(\displaystyle{ |X|}\)- liczność zbioru wierzchołków X