Matematyka.pl

Witam,
Bardzo proszę o pomoc z takim zadankiem.
Wykazać, iż graf \(\displaystyle{ G = (V, E)}\) jest spójny wtedy i tylko wtedy gdy dla każdego podziału zbioru \(\displaystyle{ V}\)na niepuste podzbiory \(\displaystyle{ V_{1} V _{2}}\) istnieje krawędź xy taka, że \(\displaystyle{ x \in V_{1}}\), a \(\displaystyle{ y \in V _{2}}\).

\(\displaystyle{ "\Rightarrow"}\)

Oczywiście jeśli istnieją dwa takie podzbiory, że \(\displaystyle{ V(G)=V_1 \cup V_2}\) i \(\displaystyle{ \forall_{x\in V_1, y \in V_2} ~~ xy \notin E(G)}\), to dla dowolnego wierzchołka z \(\displaystyle{ V_1}\) nie istnieje ścieżka do żadnego elementu z \(\displaystyle{ V_2}\), a więc graf jest niespójny. Sprzeczność

\(\displaystyle{ "\Leftarrow"}\)

Załóżmy, że graf jest spójny i podzielmy go na \(\displaystyle{ V_1, V_2}\). Ze spójności mamy, że dla \(\displaystyle{ x \in V_1, y \in V_2}\) istnieje ścieżka je łącząca \(\displaystyle{ x=x_1, x_2, \dots, x_k=y}\). Wtedy idziemy po tej ścieżce tak długo, aż natrafimy na krawędź pomiędzy \(\displaystyle{ V_1}\) i \(\displaystyle{ V_2}\) (w końcu to nastąpi, bo \(\displaystyle{ y=x_k \in V_2}\)