Vi har sett exempel på anslutna grafer och grafer som inte är anslutna. Även om ”inte sammanlänkad” är en ganska stor återvändsgränd finns det mycket att säga om ”hur sammanlänkad” en sammanlänkad graf är.Den enklaste metoden är att titta på hur svårt det är att koppla bort en graf genom att ta bort hörn eller kanter. Vi antar att alla grafer är enkla.
Om det är möjligt att koppla bort en graf genom att ta bort en enda topp, som kallas för en snittpunkt, säger vi att grafen har konnektivitet1. Om detta inte är möjligt, men det är möjligt att koppla bort grafen genom att ta bort två toppar, har grafen konnektivitet 2.
Vi gör samma sak för kanter:
Sats 5.7.3 $\kappa(G)\le\lambda(G)$.
Grafer som är 2-anslutna är särskilt viktiga, och följande enkla sats är användbar.
Det finns andra trevliga karakteriseringar av 2-anslutna grafer.
Den följande följden är en enkel omformulering av denna sats.
Denna version av satsen föreslår en generalisering:
Vi bevisar först Mengers ursprungliga version av detta, en ”lokal” version.
Sats 5.7.9 Om $v$ och $w$ är icke angränsande hörn i $G$, $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet\quad\bullet\quad\bullet\quad\bullet$$$
Vi återvänder kort till 2-konnektivitet. nästa sats kan ibland användas för att tillhandahålla induktionssteget i ett induktionsbevis.
En graf som inte är konnekter består av konnekterade komponenter. I ett atheorem som påminner om detta ser vi att anslutna grafer som inte är2-anslutna är konstruerade av 2-anslutna undergrafer och broar.
Definition 5.7.11 Ett block i en graf $G$ är en maximaltinducerad undergraf på minst två hörn utan en skärningspunkt.
Som vanligt betyder maximalt här att den inducerade undergrafen $B$ inte kan göras större genom att lägga till hörn eller kanter (samtidigt som den önskade egenskapen bibehålls, i detta fall inga skärningspunkter).Ett block är antingen en inducerad undergraf med två anslutningar eller en enskild kant tillsammans med dess ändpunkter. Blocken är användbara till stor del på grund av denna sats:
Sats 5.7.12 Blocken i $G$ delar upp kanterna.
Om $G$ har ett enda block är det antingen $K_2$ eller är 2-anslutet, och varje 2-ansluten graf har ett enda block.
Sats 5.7.13 Om $G$ är sammanlänkad men inte2-ansluten är varje topp som ligger i två block en skärningspunkt i $G$.
Övningar 5.7
Ex 5.7.1Antag att en enkel graf $G$ på $n\ge 2$ hörn har minst$\ds {(n-1)(n-2)\over2}+1$ kanter. Bevisa att $G$ är sammanhängande.
Ex 5.7.3Förutsatt att $G$ är enkel med en gradsekvens$d_1\le d_2\le\cdots\le d_n$, och för $k\le n-d_n-1$, $d_k\ge k$. Visa att $G$ är sammanhängande.
Ex 5.7.4Har vi kommit ihåg att en graf är $k$-reguljär om alla hörn har graden $k$. Vilket är det minsta heltal $k$ som gör detta sant:
Om $G$ är enkel, har $n$ hörn, $m\ge k$ och $G$ är $m$-reguljärt, så är $G$ sammanhängande.
(Naturligtvis beror $k$ på $n$.)
Ex 5.7.6Finn en enkel graf med $\kappa(G)
Notera att en skärningspunkt ingår i minst två block, så att alla hörande hörn i grafen med block- och skärningspunkt är block. Dessa block kallas slutblock.
Ex 5.7.10Teckna upp block- och skärningspunktsgrafen för grafen nedan.