Vi har set eksempler på sammenhængende grafer og grafer, der ikke er sammenhængende. Selv om “ikke forbundet” er en temmelig blindgyde, er der meget at sige om “hvor forbundet” en forbundet graf er.Den enkleste fremgangsmåde er at se på, hvor svært det er at afbryde en graf ved at fjerne hjørner eller kanter. Vi antager, at alle grafer er simple.
Hvis det er muligt at afbryde forbindelsen til en graf ved at fjerne et enkelt toppunkt, kaldet et cutpoint, siger vi, at grafen har konnektivitet1. Hvis dette ikke er muligt, men det er muligt at afbryde grafen ved at fjerne to toppunkter, har grafen konnektivitet 2.
Vi gør det samme for kanter:
Sætning 5.7.3 $\kappa(G)\le\lambda(G)$.
Grafer, der er 2-tilsluttede, er særligt vigtige, og følgende simple sætning er nyttig.
Der findes andre fine karakteriseringer af 2-forbundne grafer.
Den følgende følgesætning er en nem omformulering af denne sætning.
Denne version af sætningen lægger op til en generalisering:
Vi beviser først Mengers oprindelige version af denne, en “lokal” version.
Sætning 5.7.9 Hvis $v$ og $w$ er ikke-tilstødende toppunkter i $G$, er $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet\quad\quad\bullet\quad\bullet$$$
Vi vender kort tilbage til 2-forbindelighed. den næste sætning kan undertiden bruges til at levere induktionstrinnet i et induktionsbevis.
En graf, der ikke er forbundet, består af forbundne komponenter. I et sætning, der minder om dette, ser vi, at sammenhængende grafer, der ikke er2-sammenkoblede, er konstrueret af 2-sammenkoblede undergrafer og broer.
Definition 5.7.11 En blok i en graf $G$ er en maksimaltinduceret undergraf på mindst to toppunkter uden et skæringspunkt.
Som sædvanlig betyder maksimalt her, at den inducerede undergraf $B$ ikke kan gøres større ved at tilføje toppunkter eller kanter (samtidig med at den ønskede egenskab, i dette tilfælde ingen skæringspunkter, bibeholdes).En blok er enten en induceret undergraf med to forbindelser eller en enkelt kant sammen med dens endepunkter. Blokke er nyttige i stor udstrækning på grund af denne sætning:
Sætning 5.7.12 Blokkene i $G$ opdeler kanterne.
Hvis $G$ har en enkelt blok, er den enten $K_2$ eller er 2-forbundet, og enhver 2-forbundet graf har en enkelt blok.
Sætning 5.7.13 Hvis $G$ er forbundet, men ikke2-forbundet, så er ethvert toppunkt, der ligger i to blokke, et skæringspunkt i $G$.
Opgaver 5.7
Ex 5.7.1Sæt, at en simpel graf $G$ på $n\ge 2$ toppene har mindst$\ds {(n-1)(n-2)\over2}+1$ kanter. Bevis, at $G$ er forbundet.
Ex 5.7.3Sæt, at $G$ er simpel med en gradsrækkefølge$d_1\le d_2\le\cdots\le d_n$, og for $k\le n-d_n-1$, $d_k\ge k$. Vis, at $G$ er forbundet.
Ex 5.7.4Husk, at en graf er $k$-regulær, hvis alle toppene har grad $k$. Hvad er det mindste hele tal $k$, der gør dette sandt:
Hvis $G$ er simpel, har $n$ hjørner, $m\ge k$, og $G$ er $m$-regulær, så er $G$ forbundet.
(Selvfølgelig afhænger $k$ af $n$.)
Ex 5.7.6Find en simpel graf med $$\kappa(G)
Bemærk, at et skæringspunkt er indeholdt i mindst to blokke, således at alle tilhørende hjørner i blok-skæringspunkt-grafen er blokke. Disse blokke kaldes endeblokke.
Ex 5.7.10Tegn blok-klippunktsgrafen for grafen nedenfor.