Abbiamo visto esempi di grafi connessi e grafi non connessi. Mentre “non connesso” è praticamente un vicolo cieco, c’è molto da dire su “quanto è connesso” un grafo connesso.L’approccio più semplice è guardare quanto è difficile disconnettere un grafo rimuovendo vertici o bordi. Assumiamo che tutti i grafi siano semplici.
Se è possibile disconnettere un grafo rimuovendo un singolo vertice, chiamato cutpoint, diciamo che il grafo ha connettività1. Se questo non è possibile, ma è possibile disconnettere il grafico rimuovendo due vertici, il grafico ha connettività 2.
Facciamo la stessa cosa per i bordi:
Teorema 5.7.3 $\kappa(G)\le\lambda(G)$.
I grafi che sono connessi in 2 sono particolarmente importanti, e il seguente semplice teorema è utile.
Ci sono altre belle caratterizzazioni dei grafi a 2 connessioni.
Il seguente corollario è una facile riaffermazione di questo teorema.
Questa versione del teorema suggerisce una generalizzazione:
Prima proviamo la versione originale di Menger, una versione “locale”.
Teorema 5.7.9 Se $v$ e $w$ sono vertici non adiacenti in $G$, $\kappa_G(v,w)=p_G(v,w)$.
$$bullo\quadro\bullo$$
Torniamo brevemente alla connettività 2. Il prossimo teorema può talvolta essere usato per fornire il passo di induzione in una prova di induzione.
Un grafico che non è connesso consiste di componenti connesse. In un teorema che ricorda questo, vediamo che i grafi connessi che non sono2-connessi sono costruiti da sottografi 2-connessi e ponti.
Definizione 5.7.11 Un blocco in un grafo $G$ è un sottografo massimale indotto su almeno due vertici senza un punto di taglio.
Come al solito, massimo qui significa che il sottografo indotto $B$ non può essere ingrandito aggiungendo vertici o bordi (pur mantenendo la proprietà desiderata, in questo caso, nessun punto di taglio).Un blocco è o un sottografo indotto collegato a due vertici o un singolo bordo insieme ai suoi punti finali. I blocchi sono utili in gran parte grazie a questo teorema:
Teorema 5.7.12 I blocchi di $G$ dividono i bordi.
Se $G$ ha un singolo blocco, o è $K_2$ o è 2connesso, e ogni grafico 2connesso ha un singolo blocco.
Teorema 5.7.13 Se $G$ è connesso ma non2-connesso, allora ogni vertice che si trova in due blocchi è un punto di taglio di $G$.
Esercizi 5.7
Ex 5.7.1Supponiamo che un grafo semplice $G$ su $n\ge 2$ abbia almeno $\ds {(n-1)(n-2)\su2}+1$ bordi. Dimostrare che $G$ è connesso.
Ex 5.7.3Supponiamo che $G$ sia semplice con sequenza di gradi$d_1\le d_2\le\cdots\le d_n$, e per $k\le n-d_n-1$, $d_k\ge k$. Dimostrare che $G$ è connesso.
Ex 5.7.4Ricordo che un grafico è $k$-regolare se tutti i vertici hanno grado $k$. Qual è il più piccolo intero $k$ che lo rende vero:
Se $G$ è semplice, ha $n$ vertici, $magra k$, e $G$ è $m$-regolare, allora $G$ è connesso.
(Naturalmente $k$ dipende da $n$.)
Ex 5.7.6Trovare un grafo semplice con $kappa(G)
Nota che un punto di taglio è contenuto in almeno due blocchi, così che tutti i vertici dipendenti del grafo a punti di taglio sono blocchi. Questi blocchi sono chiamati blocchi finali.
Ex 5.7.10Disegna il grafo a blocchi e punti di taglio del grafico sottostante.