We hebben voorbeelden gezien van verbonden en niet-verbonden grafieken. Hoewel “niet verbonden” vrijwel een doodlopende weg is, valt er veel te zeggen over “hoe verbonden” een verbonden grafiek is. De eenvoudigste benadering is te kijken hoe moeilijk het is een grafiek te ontkoppelen door hoekpunten of ribben te verwijderen. We nemen aan dat alle grafieken eenvoudig zijn.
Als het mogelijk is een grafiek te ontkoppelen door een enkel hoekpunt te verwijderen, een zogenaamd snijpunt, dan zeggen we dat de grafiek connectiviteit1 heeft. Als dit niet mogelijk is, maar het wel mogelijk is de grafiek te ontkoppelen door twee hoekpunten te verwijderen, heeft de grafiek connectiviteit 2.
Hetzelfde doen we voor de ribben:
Stelling 5.7.3 $\kappa(G)\le-lambda(G)$.
Grafieken die 2-connectief zijn, zijn bijzonder belangrijk, en de volgende eenvoudige stelling is dan nuttig.
Er zijn nog andere aardige karakteriseringen van 2-verbonden grafen.
De volgende corollary is een eenvoudige herformulering van deze stelling.
Deze versie van de stelling suggereert een veralgemening:
We bewijzen eerst Menger’s oorspronkelijke versie hiervan, een “lokale” versie.
Stelling 5.7.9 Als $v$ en $w$ niet-aangrenzende hoekpunten in $G$ zijn, geldt $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet$
We keren kort terug naar 2-connectiviteit.De volgende stelling kan soms gebruikt worden om de inductiestap in een inductiebewijs te geven.
Een grafiek die niet verbonden is, bestaat uit verbonden componenten. In een stelling die hierop lijkt, zien we dat verbonden grafen die niet2verbonden zijn, geconstrueerd worden uit 2-verbonden deelgrafieken en bruggen.
Definitie 5.7.11 Een blok in een grafiek $G$ is een maximaal geïnduceerde deelgrafiek op ten minste twee hoekpunten zonder snijpunt.
Zoals gebruikelijk betekent maximaal hier dat de geïnduceerde subgraaf $B$ niet groter kan worden gemaakt door vertices of ribben toe te voegen (met behoud van de gewenste eigenschap, in dit geval geen snijpunten).Een blok is ofwel een geïnduceerde subgraaf met twee verbindingen ofwel een enkele rand samen met zijn eindpunten. Blokken zijn vooral nuttig omwille van deze stelling:
Stelling 5.7.12 De blokken van $G$ verdelen de ribben.
Als $G$ een enkel blok heeft, dan is het ofwel $K_2$ ofwel 2-verbonden, en elke 2-verbonden grafiek heeft een enkel blok.
Stelling 5.7.13 Als $G$ verbonden maar niet 2-verbonden is, dan is elk hoekpunt dat zich in twee blokken bevindt een snijpunt van $G$.
Oefeningen 5.7
Ex 5.7.1Voorstel dat een eenvoudige grafiek $G$ op $n:2$ hoekpunten ten minste$n:ds {(n-1)(n-2)\over2}+1$ ribben heeft. Bewijs dat $G$ verbonden is.
Ex 5.7.3Voorstel dat $G$ eenvoudig is met een gradenreeks van $d_1le d_2$, en dat voor $k_le n-d_n-1$, $d_k_000x k$ is. Laat zien dat $G$ verbonden is.
Ex 5.7.4Herinner je dat een grafiek $k$regelmatig is als alle hoekpunten graad $k$ hebben. Wat is het kleinste gehele getal $k$ dat dit waar maakt:
Als $G$ eenvoudig is, $n$ hoekpunten heeft, $mvolledig k$, en $G$ is $m$regelmatig, dan is $G$ verbonden.
(Natuurlijk hangt $k$ af van $n$.)
Ex 5.7.6Vind een eenvoudige grafiek met $kappa(G)
Merk op dat een snijpunt in minstens twee blokken ligt, zodat alle loodrechte hoekpunten van de blok-knippuntgrafiek blokken zijn. Deze blokken worden eindblokken genoemd.
Ex 5.7.10Teken de blok-snijpuntgrafiek van de onderstaande grafiek.