Zarówno drzewo, jak i klika są grafami spójnymi. W drzewie jednak, usunięcie jakiegokolwiek wierzchołka nie będącego liściem rozspaja go. Z drugiej strony, klika pozostaje spójna po usunięciu dowolnej liczby wierzchołków. Aby rozróżnić te różne rodzaje spójności rozważa się następujące uogólnienia spójności.
Graf k-spójny to graf, który po usunięciu dowolnie wybranych k−1 wierzchołków (i incydentnych z nimi krawędzi) pozostaje spójny.
Graf k-spójny krawędziowo to graf, który po usunięcie dowolnie wybranych k−1 krawędzi (bez usuwania wierzchołków) pozostaje spójny.
Przykład
Z pojęciami wielospójności związane są następujące pojęcia:
Zbiór rozdzielający wierzchołki u,v to zbiór wierzchołków S⊆V−{u,v} taki, że każda droga z u do v przechodzi przez któryś element ze zbioru S.
Ponadto powiemy, że S jest zbiorem rozdzielającym, jeśli S jest zbiorem rozdzielającym jakichś dwu wierzchołków u,v.
Zbiór rozspajający wierzchołki u,v to zbiór krawędzi F⊆E taki, że każda droga z u do v zawiera jakąś krawędź z F.
Rozcięcie wierzchołków u,v to zbiór rozspajający wierzchołki u,v, którego żaden podzbiór właściwy nie rozspaja u z v.
Zbiór krawędzi F będziemy nazywać rozcięciem, jeśli F jest rozcięciem jakichś dwu wierzchołków u,v
Most to taka krawędź e, że zbiór {e} tworzy rozcięcie.
Uwaga
Jeżeli graf jest k-spójny, to każdy jego zbiór rozdzielający musi mieć co najmniej k wierzchołków. Analogicznie jeśli G jest k-spójny krawędziowo, to każde jego rozcięcie musi mieć co najmniej k krawędzi.
Przykład
Przykładowymi zbiorami rozdzielającymi wierzchołki u,w w grafie z rysunku Grafy menger są zbiory {x,y,z} i {s,t}. Zbiory {xs,xy,ys,ys,zt} jest rozspajający, a zbiór {xs,xy,uy,uz} jest rozcięciem. Graf ten jest 2-spójny oraz 2-spójny krawędziowo.
Okazuje się, że dla dwu różnych wierzchołków istnieje powiązanie - między wielkością rozcięcia, a liczbą dróg pomiędzy nimi - silniejsze niż to wynikające z definicji.
Twierdzenie 13.8 [Menger 1927]
Największa możliwa liczba krawędziowo rozłącznych dróg łączących dwa różne niesąsiednie wierzchołki grafu spójnego, jest równa najmniejszej liczbie krawędzi w zbiorze rozspajającym te wierzchołki.
Dowód
Niech w,u będą dwoma różnymi i niesąsiednimi wierzchołkami grafu spójnego G=(V,E). Przez k oznaczmy najmniejszą możliwą liczność zbioru krawędzi rozspajającego w,u. Oczywiście każda droga łącząca w z u musi przejść przez każdy zbiór rozspajający. A zatem dróg krawędziowo rozłącznych łączących w z u nie może być więcej niż k. Tak więc wystarczy pokazać, że istnieje k rozłącznych krawędziowo dróg z w do u.
Dowód przeprowadzimy indukcyjnie ze względu na liczbę krawędzi w grafie G rozważając dwa przypadki.
1. Pewien zbiór rozspajający X mocy k ma krawędź nie incydentną z w oraz ma krawędź (być może inną) nie incydentną z u.
Graf G, po usunięciu wszystkich krawędzi z X, podzieli się na dwie spójne składowe W oraz U, do których odpowiednio należą w i u.
Przez W′ oznaczmy graf powstały z grafu G poprzez ściągnięcie U w jeden wierzchołek u′. Wtedy u′ jest połączony z tymi wierzchołkami t∈W, z którymi połączony był jakiś wierzchołek s∈U. Warto zauważyć, że wtedy musiało być st∈X. Krawędzie łączące wierzchołki wewnątrz W pozostały niezmienione. Graf U′ definiujemy analogicznie, poprzez ściągnięcie zbioru W do wierzchołka w′.
W grafie W′ zbiór krawędzi incydentnych z u′, których jest k, tworzy minimalny zbiór rozspajający wierzchołki w,u′. Ponieważ założyliśmy, że w X istnieje krawędź nieincydentna z u, to U ma co najmniej dwa wierzchołki, a zatem graf W′ ma mniej krawędzi niż G. Tak więc możemy skorzystać z założenia indukcyjnego otrzymując k rozłącznych krawędziowo dróg łączących w z u′. Analogicznie w grafie U′ otrzymujemy k rozłącznych krawędziowo dróg łączących w′ z u. Sklejając obie te rodziny dróg otrzymujemy k rozłącznych ścieżek łączących w z u w grafie G.
2. W każdym zbiorze rozspajającym X o mocy k każda krawędź jest incydentna do w lub do u.
Możemy wtedy założyć, że G zawiera jedynie krawędzie należące do któregoś zbioru rozspajającego w,u o liczności k. Gdyby tak nie było i istniałaby jakaś inna krawędź e, to moglibyśmy e usunąć i, na mocy założenia indukcyjnego, otrzymać natychmiast k rozłącznych dróg łączących w,u. Tak więc pozostały nam jedynie te krawędzie, które są w minimalnych zbiorach rozspajających w,u. To zaś, zgodnie z założeniem przypadku 2 oznacza, że każda krawędź jest incydentna z w lub z u. W ten sposób drugi przypadek sprowadziliśmy do sytuacji, w której każda ścieżka z w do u ma co najwyżej dwie krawędzie. Wśród takich ścieżek nietrudno jest już wskazać k rozłącznych krawędziowo.
Jako ćwiczenie 9 pozostawiamy dowód twierdzenia analogicznego do Twierdzenia 13.8, a wiążącego tym razem zbiory rozdzielające z drogami rozłącznymi wierzchołkowo.
Twierdzenie 13.9
Największa możliwa liczba wierzchołkowo rozłącznych dróg łączących dwa różne niesąsiednie wierzchołki grafu spójnego, jest równa najmniejszej liczbie wierzchołków w zbiorze rozdzielającym te wierzchołki.
Z Twierdzenia 13.9, można w łatwy sposób wywnioskować Twierdzenia 13.7, o skojarzeniach w grafach dwudzielnych. Wyprowadzenie to pozostawiamy jako ćwiczenie 10.
W grafie k-spójnym usunięcie jakichś k−1 punktów nie rozspaja go. A zatem zbiór rozdzielający jakieś dwa wierzchołki w,u ma co najmniej k wierzchołków. Tym samym między u a w musi istnieć co najmniej k dróg. Pisząc zwięźlej możemy powiedzieć, że:
Wniosek 13.10
Graf z co najmniej k+1 wierzchołkami jest k-spójny wtedy i tylko wtedy, gdy dowolne dwa wierzchołki są połączone przynajmniej k drogami wierzchołkowo rozłącznymi.
Analogiczne rozumowanie przeprowadzone dla ścieżek rozłącznych krawędziowo prowadzi do następującego wniosku.
Wniosek 13.11
Graf z co najmniej k−1 krawędziami jest k-spójny krawędziowo wtedy i tylko wtedy, gdy dowolne dwa wierzchołki są połączone przynajmniej k drogami krawędziowo rozłącznymi.