Corrigé Centrale 2026 Option informatique MP — Partie B, III (Q31 à Q43) : Graphes planaires, formule d'Euler, cinq couleurs

On note $n=|S|$, $m=|A|$ et $|F|$ le nombre de faces d'un dessin planaire fixé.

Q31. Sommets. Chaque arête $\{u,v\}$ contient exactement deux sommets, donc contribue pour $1$ à $\mathrm{deg}(u)$ et pour $1$ à $\mathrm{deg}(v)$ :

$$\sum _{s\in S}\mathrm{deg}(s)=2|A|.$$

Faces. Chaque arête a deux côtés. Si elle est sur un cycle, ses deux côtés bordent deux faces distinctes et elle est parcourue une fois dans le parcours de frontière de chacune ; sinon (arête dont la suppression déconnecte le graphe, comme $cd$ dans la figure 4), la même face la borde des deux côtés et le parcours minimal de sa frontière l'emprunte deux fois, à l'aller et au retour (un parcours fermé qui franchit une telle arête doit la refranchir pour revenir). Dans les deux cas, chaque arête compte exactement deux fois dans la somme des degrés des faces :

$$\sum _{f\in F}\mathrm{deg}(f)=2|A|.$$

Vérification sur la figure 4 : sommets $2+2+3+3+2+2=14$, faces $3+3+8=14$, et $|A|=7$ ; l'arête $cd$ est comptée deux fois dans le degré $8$ de la face 3.

Q32. Un arbre est un graphe connexe sans cycle. Montrons par récurrence sur $n\ge 1$ qu'un arbre à $n$ sommets a $n-1$ arêtes et que tout dessin planaire de l'arbre a une seule face ; la formule en découle : $n-(n-1)+1=2$.

Initialisation. Pour $n=1$ : aucune arête, et le plan privé d'un point est connexe par arcs : une face.

Hérédité. Soit $T$ un arbre à $n+1\ge 2$ sommets. Il possède une feuille (sommet de degré $1$) : l'extrémité $x$ d'un chemin élémentaire de longueur maximale a pour seul voisin son prédécesseur sur le chemin, car un autre voisin hors du chemin prolongerait le chemin et un autre voisin sur le chemin fermerait un cycle. Ôtons $x$ et son unique arête : on obtient un graphe $T^{\prime }$ à $n$ sommets, sans cycle, et connexe (un chemin entre deux sommets de $T^{\prime }$ ne passe pas par la feuille $x$, qui n'a qu'un voisin). Par hypothèse de récurrence, $T^{\prime }$ a $n-1$ arêtes, donc $T$ en a $n$. Dans le dessin, l'arête de $x$ est un arc qui ne touche le reste du tracé qu'en une extrémité : l'ôter du plan privé du dessin de $T^{\prime }$ (une seule face) ne le déconnecte pas, donc le dessin de $T$ a encore une seule face.

Q33. Récurrence sur $k=m-n+1$, pour les graphes connexes planaires dessinés. Un graphe connexe a au moins $n-1$ arêtes (il contient un arbre couvrant, obtenu en ôtant des arêtes de cycles tant qu'il en existe ; il a $n-1$ arêtes par Q32), donc $k\ge 0$.

Cas $k=0$. Le graphe est connexe à $n-1$ arêtes : c'est un arbre (s'il avait un cycle, ôter une arête du cycle donnerait un graphe connexe à $n-2$ arêtes, impossible). La formule est Q32.

Hérédité. Si $k\ge 1$, $G$ n'est pas un arbre (sinon $m=n-1$) : il contient un cycle $C$. Soit $e$ une arête de $C$. Le graphe $G-e$ est connexe (le reste de $C$ relie les extrémités de $e$), planaire (on garde le même dessin), et a $k-1$ pour valeur du paramètre. Le cycle $C$ est dessiné comme une courbe fermée simple, qui sépare le plan en un intérieur et un extérieur (théorème de Jordan, admis) : les deux côtés de $e$ appartiennent donc à deux faces distinctes $f_1$ (dans l'intérieur) et $f_2$ (dans l'extérieur). En supprimant $e$, ces deux faces fusionnent (on peut désormais passer de l'une à l'autre à travers l'ancienne arête), les autres faces sont inchangées : $G-e$ a $|F|-1$ faces. Par hypothèse de récurrence, $n-(m-1)+(|F|-1)=2$, c'est-à-dire $n-m+|F|=2$.