Graf 2spojny wierzcholkowo

[Matiks21]

Witam,

Mam takie oto twierdzenie.

Graf jest 2-spójny wierzcholkowo wtw gdy każda para wiercholkow znajduje się w tym samym cyklu.

Nie za bardzo rozumiem co mówi to twierdzenie ani jak się za nie zabrać. Mogę prosić o pomoc?

[MatXXX]

Graf jest \(\displaystyle{ k}\)-spójny (wierzchołkowo) wtedy, kiedy po usunięciu \(\displaystyle{ k-1}\) wierzchołków pozostaje spójny. Czyli w 2-spójnym usunięcie jednego wierzchołka nie powinno powodować rozspójnienia.

Graf jest spójny, kiedy dla dowolnej pary wierzchołków istnieje ścieżka, która je łączy.

Skoro nasz graf jest spójny, to istnieje ścieżka pomiędzy dowolną parą wierzchołków. Jest on również 2-spójny, więc po usunięciu pewnego wierzchołka (dowolnego, ale nie z naszej pary, bo wtedy dalsze rozważanie nie ma sensu) ścieżka pomiędzy wierzchołkami tamtej pary również istnieje. Jednak usunięty wierzchołek mógł być częścią jednej ze ścieżek pomiędzy wierzchołkami, a więc takich ścieżek przed usunięciem było dwie lub więcej (zbiory wierzchołków tych ścieżek muszą być rozłączne). Czyli mamy 2 rozłączne ścieżki (możemy z nich wybrać drogi) pomiędzy dwoma wierzchołkami, a więc istnieje cykl (z tychże dróg).

[Matiks21]

Dlaczego te ścieżki muszą być rozlączne?

[Hydra147]

Może inaczej. Istnieją co najmniej dwie ścieżki. Gdyby pokazać, że co najmniej dwie z nich są rozłączne to mielibyśmy tezę. Ale przecież gdyby tak nie było, to wszystkie miałyby wspólną krawędź. Ale wówczas usunięcie jej spowodowałoby rozspójnienie grafu, czyli nie byłby 2-spójny.

[Matiks21]

To co piszesz jest nieprawdziwe. To że nie są rozlacze wcale nie znaczy że wszystkie muszą łączyć się w pewnym wierzchołku-- 12 lip 2015, o 19:23 --Przepraszam pomyliłem się.