Nous avons vu des exemples de graphes connectés et de graphes qui ne sont pas connectés. L’approche la plus simple est de regarder à quel point il est difficile de déconnecter un graphe en enlevant des sommets ou des arêtes. Nous supposons que tous les graphes sont simples.
S’il est possible de déconnecter un graphe en enlevant un seul sommet,appelé point de coupure, on dit que le graphe a une connectivité1. Si cela n’est pas possible, mais qu’il est possible de déconnecter le grapheen enlevant deux sommets, le graphe a une connectivité 2.
On fait la même chose pour les arêtes :
Théorème 5.7.3 $\kappa(G)\le\lambda(G)$.
Les graphes qui ont une connectivité 2 sont particulièrement importants, et le théorème simple suivant est utile.
Il existe d’autres caractérisations agréables des graphes à 2 connexions.
Le corollaire suivant est une reformulation facile de ce théorème.
Cette version du théorème suggère une généralisation:
Nous prouvons d’abord la version originale de Menger, une version « locale ».
Théorème 5.7.9 Si $v$ et $w$ sont des sommets non adjacents dans $G$, $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet\quad\bullet\quad\bullet$$
Nous revenons brièvement sur la 2-connectivité.Le théorème suivant peut parfois être utilisé pour fournir l’étape d’inductiondans une preuve par induction.
Un graphe qui n’est pas connecté est constitué de composantes connectées. Dans un théorème rappelant ceci, on voit que les graphes connectés qui ne sont pas2-connectés sont construits à partir de sous-graphes 2-connectés et de ponts.
Définition 5.7.11 Un bloc dans un graphe $G$ est un sous-graphe maximalinduit sur au moins deux sommets sans point de coupure.
Comme d’habitude, maximal signifie ici que le sous-graphe induit $B$ ne peut pas être rendu plus grand en ajoutant des sommets ou des arêtes (tout en conservant la propriété désirée, dans ce cas, aucun point de coupure).Un bloc est soit un sous-graphe induit à 2 connexions, soit une seule arête avec ses points d’extrémité. Les blocs sont utiles en grande partie grâce à ce théorème :
Théorème 5.7.12 Les blocs de $G$ partitionnent les arêtes.
Si $G$ a un seul bloc, il est soit $K_2$, soit 2-connecté, et tout graphe 2-connecté a un seul bloc.
Théorème 5.7.13 Si $G$ est connecté mais non2-connecté, alors tout sommet qui est dans deux blocs est un point de coupe de$G$.
Exercices 5.7
Ex 5.7.1Supposons qu’un graphe simple $G$ sur $n\ge 2$ sommets possède au moins$\ds {(n-1)(n-2)\over2}+1$ arêtes. Prouvez que $G$ est connexe.
Ex 5.7.3Supposez que $G$ est simple avec une suite de degrés$d_1\le d_2\le\cdots\le d_n$, et pour $k\le n-d_n-1$, $d_k\ge k$. Montrer que$G$ est connexe.
Ex 5.7.4Rappelons qu’un graphe est $k$-régulier si tous les sommets ont un degré $k$. Quel est le plus petit entier $k$ qui rend ceci vrai:
Si $G$ est simple, a $n$ sommets, $m\ge k$, et $G$ est $m$-régulier,alors $G$ est connecté.
(Bien sûr $k$ dépend de $n$.)
Ex 5.7.6Trouver un graphe simple avec$\kappa(G)
Notez qu’un point de coupe est contenu dans au moins deux blocs, de sorte que tous les sommets pendants du graphe bloc-point de coupe sont des blocs. Ces blocs sont appelés blocs d’extrémité.
Ex 5.7.10Dessinez le graphe bloc-point de coupe du graphe ci-dessous.
.