Matematyka.pl

\(\displaystyle{ (V,E)}\) - drzewo \(\displaystyle{ G}\), \(\displaystyle{ (V_1,E_1), (V_2,E_2), (V_3,E_3),}\) spójne podgrafy \(\displaystyle{ G}\). Pokazać, że jeśli \(\displaystyle{ \bigwedge (1 \le i, j \le 3) V_i \cap V_j \neq \emptyset}\) to \(\displaystyle{ V_1 \cap V_2 \cap V_3 \neq \emptyset}\).

Próbowałam to robić jakoś tak, że biorę dowolny wierzchołek \(\displaystyle{ x}\) z \(\displaystyle{ V_1 \cap V_2}\). Istnieje droga między x i dowolnym wierzchołkiem z \(\displaystyle{ V_1}\) oraz między \(\displaystyle{ x}\) i dowolnym wierzchołkiem z \(\displaystyle{ V_2}\), bo grafy te są spójne.

Biorę dowolny wierzchołek \(\displaystyle{ y}\) z \(\displaystyle{ V_2 \cap V_3}\). Istnieje droga między \(\displaystyle{ x}\) i \(\displaystyle{ y}\), bo oba należą do \(\displaystyle{ V_2}\). Jest tylko jedna taka drogą, bo inaczej powstałby cykl.

Biorę dowolny wierzchołek \(\displaystyle{ z}\) z \(\displaystyle{ V_1 \cap V_3}\). Istnieje droga między \(\displaystyle{ x}\) i \(\displaystyle{ z}\), bo oba należą do \(\displaystyle{ V_1}\). Jest tylko jedna taka drogą, bo inaczej powstałby cykl.

Te drogi muszą mieć część wspólną, bo nie ma cykli, czyli \(\displaystyle{ V_1 \cap V_2 \cap V_3 \neq \emptyset}\).


Nie wiem, jak tę końcówkę do końca uzasadnić. I proszę o pomoc, czy ogólnie ten dowód ma mniej więcej sens.

Załóżmy nie wprost, że ten przekrój jest pusty
Usuńmy z G \(\displaystyle{ V_1\cap V_2}\), wtedy każda spójna składowa tego co pozostanie zawiera wierzchołki z co najwyżej jednego ze zbiorów \(\displaystyle{ V_1, V_2}\) (to wymaga uzasadnienia). No, a \(\displaystyle{ V_3}\) musi być zawarty w pewnej takiej składowej (bo kroi się pusto z wyrzuconym \(\displaystyle{ V_1\cap V_2}\)). Sprzeczność.

Dziękuję.

Jakby jeszcze ktoś mógł powiedzieć, czy mój pomysł też był dobry, czy zły, to byłoby super.

Te drogi o których piszesz mają część wspólną: jest w niej \(\displaystyle{ x}\). Ale dlaczego z tego ma coś wynikać o niepustości: \(\displaystyle{ V_1\cap V_2 \cap V_3}\)?

Próbowałam jakoś zapisać to, że jak mam już to przecięcie \(\displaystyle{ V_1 \cap V_2}\), to \(\displaystyle{ V_3}\) można przeciąć z oboma tymi zbiorami tylko w tym zbiorze \(\displaystyle{ V_1 \cap V_2}\), inaczej jakby dodać krawędzie oddzielnie do tych zbiorów, to powstałby cykl.
Ale trochę mi nie wyszło