Widzieliśmy przykłady grafów połączonych i grafów niepołączonych. O ile „niepołączony” to ślepy zaułek, to wiele można powiedzieć o tym, „jak bardzo połączony” jest graf połączony. Najprostszym podejściem jest sprawdzenie, jak trudno jest odłączyć graf przez usunięcie wierzchołków lub krawędzi. Zakładamy, że wszystkie grafy są proste.
Jeśli możliwe jest odłączenie grafu przez usunięcie jednego wierzchołka, zwanego punktem przecięcia, mówimy, że graf ma łączność1. Jeśli nie jest to możliwe, ale możliwe jest rozłączenie grafu przez usunięcie dwóch wierzchołków, to graf ma łączność 2.
Tak samo postępujemy z krawędziami:
Twierdzenie 5.7.3 $kappa(G)$.
Grafy, które są 2-połączone są szczególnie ważne, a poniższe proste twierdzenie jest przydatne.
Istnieją inne ładne charakteryzacje grafów 2-połączonych.
Następujące następstwo jest łatwym przekształceniem tego twierdzenia.
Ta wersja twierdzenia sugeruje uogólnienie:
Najpierw udowodnimy oryginalną wersję tego twierdzenia Mengera, wersję „lokalną”.
Twierdzenie 5.7.9 Jeśli $v$ i $w$ są niesąsiadującymi wierzchołkami w $G$, to $kappa_G(v,w)=p_G(v,w)$.
$Kwadrat$
Powracamy na krótko do 2-połączalności.Następne twierdzenie może być czasem użyte do zapewnienia kroku indukcyjnego w dowodzie indukcyjnym.
Graf, który nie jest połączony, składa się z połączonych elementów. W twierdzeniu przypominającym to widzimy, że grafy połączone, które nie są 2-połączone są zbudowane z 2-połączonych podgrafów i mostów.
Definicja 5.7.11 Blok w grafie $G$ jest maksymalnie indukowanym podgrafem na co najmniej dwóch wierzchołkach bez punktu przecięcia.
Twierdzenie 5.7.12 Bloki $G$ dzielą krawędzie.
Jeśli $G$ ma pojedynczy blok, to jest albo $K_2$ albo jest 2-połączony, a każdy 2-połączony graf ma pojedynczy blok.
Twierdzenie 5.7.13 Jeśli $G$ jest połączony, ale nie2-połączony, to każdy wierzchołek, który jest w dwóch blokach jest punktem przecięcia $G$.
Ćwiczenia 5.7
Twierdzenie 5.7.1Załóżmy, że graf prosty $G$ na $n 2$ wierzchołkach ma co najmniej $ds {(n-1)(n-2)\i0}+1$ krawędzi. Udowodnij, że $G$ jest połączony.
Ex 5.7.3Załóżmy, że $G$ jest prosty z sekwencją stopni $d_1$ d_2$ i dla $k$ n-d_n-1$, $d_k$. Wykaż, że graf G$ jest połączony.
Ex 5.7.4Przypomnijmy, że graf jest $k$-regularny, jeśli wszystkie wierzchołki mają stopień $k$. Jaka jest najmniejsza liczba całkowita $k$, która czyni to prawdą:
Jeżeli $G$ jest prosty, ma $n$ wierzchołków, $m $ge k$, a $G$ jest $m$-regularny, to $G$ jest połączony.
(Oczywiście $k$ zależy od $n$.)
Ex 5.7.6Znajdujemy graf prosty z $kappa(G)
Zauważmy, że punkt przecięcia jest zawarty w co najmniej dwóch blokach, tak że wszystkie wierzchołki wiszące grafu blokowo-punktowego są blokami. Bloki te nazywamy blokami końcowymi.
Ex 5.7.10Narysuj graf blokowo-punktowy dla poniższego grafu.
.