mathématiques appliquées (ECG 1re année) · Chapitre 3 · Exercice d'entraînement

Un graphe ou son complémentaire est connexe

Théorie des graphes · Connexité · ★★★ niveau 3 (difficile)

Énoncé

Soit $G$ un graphe non orienté sans boucle à $n\ge 2$ sommets, et $\overline{G}$ le graphe où deux sommets distincts sont reliés exactement lorsqu'ils ne le sont pas dans $G$. Montrer que si $G$ n'est pas connexe, alors $\overline{G}$ l'est. Les deux peuvent-ils être connexes en même temps ?

Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.