Przechodniość rozcięć w grafie

[alef1992]

Nie wiem gdzie mógłbym zamieścić temat z teorii grafów więc piszę go tutaj. Mianowicie ostatnio spostrzegłem, że jeśli w grafie G mamy rozcięcia:
\(\displaystyle{ R_1=\{e_1,e_2\}}\) oraz \(\displaystyle{ R_2=\{e_2,e_3\}}\) gdzie \(\displaystyle{ e_i}\) to krawędzie to też \(\displaystyle{ R=\{e_1,e_3\}}\) - rozcięcie. Czy to jest prawda i jak to ewentualnie udowodnić? Próbowałem ale nie za bardzo mi wychodzi dowód.

[Kartezjusz]

Nie.Powiem więcej . Jeśli mamy rozcięcia \(\displaystyle{ R_{1}={e_{1},e_{2}}}\)oraz \(\displaystyle{ R_{2}={e_{3},e_{4}}}\) tego samego grfu takie,że \(\displaystyle{ R_{1} \cap R_{2} \neq \emptyset}\) to \(\displaystyle{ R_{1}=R_{2}}\)
Istotnie.Załóżmy, że rozcięcia są różne,ale nie rozłączne
Dla ustalenia uwagi \(\displaystyle{ e_{1}=e_{3}}\) i wówczas
\(\displaystyle{ e_{2}=G \setminus e_{1}=G \setminus e_{3}=e_{4}}\)
Mamy więc równość

[alef1992]

A na przykład weźmy graf cykliczny o 4 wierzchołkach \(\displaystyle{ C_4}\). Nazwijmy krawędzie kolejno \(\displaystyle{ e_1,e_2,e_3,e_4}\). Wówczas rozcięciem jest \(\displaystyle{ R_1=\{e_1,e_2\}}\) oraz\(\displaystyle{ R_2=\{e_2,e_3\}}\). Ale rozcięciem jest też \(\displaystyle{ R=\{e_1,e_3\}}\).
Może być problem z nazewnictwem: dla mnie rozcięcie jest najmniejszym zbiorem (krawędzi) rozspajającym (tzn. żaden jego podzbiór nie rozspójni grafu). Zbiór rozspajający to dowolny zbiór krawędzi grafu, taki, że jego usunięcie rozspójni graf.

[Kartezjusz]

\(\displaystyle{ R_{1},r_{2}}\) Otrzymasz dwie litery L ,które są grafami spójnymi

[alef1992]

Owszem \(\displaystyle{ R_1,R_2}\) są grafami spójnymi, ale chodzi o to że jak usuniemy z grafu G krawędzie należące do \(\displaystyle{ R_1}\), to graf G się rozspójni (wyrzucamy tylko krawędzie, nie wyrzucamy wierzchołków). Tak samo jeśli wyrzucimy z G krawędzie należące do \(\displaystyle{ R_2}\) to też G się rozspójni. Jak wyrzucimy z G krawędzie z \(\displaystyle{ R}\) to też G się rozspójni.

[Kartezjusz]

właśnie wywaliłem krawędzie