Un graphe ou son complémentaire est connexe

Le principe. Supposons $G$ non connexe : ses sommets se répartissent en au moins deux composantes, et deux sommets de composantes différentes ne sont reliés par aucune chaîne de $G$. Soient $u\ne v$ ; montrons qu'une chaîne de $\overline{G}$ les relie.

Premier cas : $u$ et $v$ sont dans des composantes différentes de $G$. Alors ils ne sont pas adjacents dans $G$ (une arête relierait leurs composantes, qui n'en feraient qu'une). Par définition du complémentaire, ils sont donc adjacents dans $\overline{G}$ : la chaîne $u-v$, de longueur $1$, convient.

Second cas : $u$ et $v$ sont dans la même composante $C$ de $G$. Comme $G$ n'est pas connexe, il existe une composante différente de $C$, et donc un sommet $w$ hors de $C$. Alors $u$ et $w$ sont dans des composantes différentes, donc non adjacents dans $G$, donc adjacents dans $\overline{G}$ ; de même pour $v$ et $w$. La chaîne $$u-w-v$$ est une chaîne de $\overline{G}$, de longueur $2$.

Conclusion. Dans tous les cas, deux sommets quelconques sont reliés par une chaîne de $\overline{G}$ : $\overline{G}$ est connexe.

Les deux à la fois ? Oui : la chaîne d'arêtes $\{1,2\},\{2,3\},\{3,4\}$ est connexe, et son complémentaire, d'arêtes $\{1,3\},\{1,4\},\{2,4\}$, est la chaîne $3-1-4-2$, connexe elle aussi. Le résultat interdit donc seulement que les deux soient non connexes.