L'essentiel à connaître
Un graphe connexe à $n$ sommets est un arbre si et seulement s'il a $n-1$ arêtes. Un graphe se colore avec deux couleurs si et seulement s'il n'a aucun cycle de longueur impaire : le cycle $C_6$ à 6 sommets se colore en alternant deux couleurs, le cycle $C_5$ en exige trois.
Définition : On travaille sans boucle ni arête double. Le degré d'un sommet est son nombre de voisins. Un chemin relie des sommets distincts de proche en proche ; un cycle est un chemin d'au moins trois sommets refermé par une arête, et sa longueur est son nombre d'arêtes. Un graphe est connexe si un chemin relie deux sommets quelconques ; un arbre est un graphe connexe sans cycle.
Ce sont les mots du programme d'informatique de MP2I et MPI, où « chemin » remplace la « chaîne » du programme de maths expertes du lycée. Chaque arête ayant deux extrémités, la somme des degrés vaut le double du nombre d'arêtes.
Propriété : Pour un graphe $G$ à $n$ sommets, sont équivalents : $G$ est un arbre ; deux sommets quelconques sont reliés par un unique chemin ; $G$ est connexe avec $n-1$ arêtes. Une forêt, graphe sans cycle, a $n-c$ arêtes si elle a $c$ morceaux (ses composantes connexes). Tout arbre à $n\ge2$ sommets a au moins deux feuilles, ou sommets de degré 1.
Colorer un graphe, c'est donner à chaque sommet une couleur différente de celles de ses voisins ; le nombre chromatique $\chi(G)$ est le plus petit nombre de couleurs qui suffit. Un graphe est biparti si ses sommets se rangent en deux groupes sans arête interne, autrement dit s'il se colore avec deux couleurs. L'algorithme glouton prend les sommets dans un ordre fixé et donne à chacun la plus petite couleur, numérotée à partir de 1, absente chez ses voisins déjà colorés.
À retenir : $\chi(K_n)=n$ pour le graphe complet $K_n$, à $n$ sommets deux à deux voisins. Si $G$ contient $k$ sommets deux à deux voisins, $\chi(G)\ge k$. Le glouton utilise au plus $\Delta+1$ couleurs, où $\Delta$ est le plus grand degré, mais pas forcément $\chi(G)$. Tout graphe planaire, dessinable sans croisement d'arêtes, vérifie $\chi(G)\le4$ : c'est le théorème des quatre couleurs.
Quiz : teste tes connaissances
Les questions montent en difficulté, et les trois dernières sont les plus piégeuses : lis-les jusqu'au bout.
Question 1 : Un graphe a 10 sommets, tous de degré 3. Combien a-t-il d'arêtes ?
Réponse : C. La somme des degrés, $10\times3=30$, compte chaque arête deux fois : il y a $15$ arêtes. Le piège, $30$, oublie de diviser par 2 ; $45$ est le nombre d'arêtes du graphe complet à 10 sommets.
Question 2 : Un graphe à $n$ sommets est forcément un arbre s'il est :
Réponse : A. C'est la propriété des arbres vue plus haut. Le piège B décrit une forêt, qui peut avoir plusieurs composantes connexes ; C a une arête de trop, donc un cycle.
Question 3 : Quel est le nombre chromatique du graphe complet $K_6$ ?
Réponse : D. Dans $K_6$, deux sommets quelconques sont voisins : les six portent des couleurs différentes, donc $\chi(K_6)=6$. Le piège, $4$, applique le théorème des quatre couleurs à un graphe qui n'est pas planaire.
Question 4 : Dans un arbre, on relie par une arête deux sommets $x$ et $y$ qui n'étaient pas voisins. Le nouveau graphe :
Réponse : B. L'arbre n'avait aucun cycle, donc tout cycle passe par $xy$ et se referme par le chemin de $y$ à $x$ dans l'arbre, qui est unique : le cycle l'est donc aussi. Le piège A oublie qu'un arbre à $n$ sommets a $n-1$ arêtes, pas une de plus.
Question 5 : Lequel de ces graphes a un nombre chromatique égal à $3$ ?
Réponse : A. Deux couleurs alternées autour de $C_7$ coincent le septième sommet entre deux voisins de couleurs différentes, car 7 est impair : il en faut une troisième. Le piège $C_8$ se colore avec deux couleurs, car 8 est pair.
Question 6 : Une forêt a 20 sommets et 4 composantes connexes. Combien a-t-elle d'arêtes ?
Réponse : D. Chaque composante est un arbre de $n_i$ sommets et $n_i-1$ arêtes ; au total, $20-4=16$. Le piège, $19$, applique la formule de l'arbre à toute la forêt, comme si elle était connexe.
Question 7 : Au minimum, combien de feuilles a un arbre à $n\ge2$ sommets ?
Réponse : C. Les deux extrémités d'un plus long chemin de l'arbre sont des feuilles, sinon on pourrait le prolonger ou fermer un cycle ; un arbre en forme de chemin en a exactement 2. Le piège, $1$, oublie la seconde extrémité.
Question 8 : Un graphe a 8 sommets et 8 arêtes. Que peut-on affirmer à coup sûr ?
Réponse : B. Sans cycle, ce serait une forêt, donc au plus $n-1=7$ arêtes. Le piège A est faux : un cycle à 5 sommets et un triangle séparé font 8 sommets, 8 arêtes et deux composantes.
Question 9 : Un arbre a 10 sommets, dont un de degré 5. Quel est son nombre chromatique ?
Réponse : A. Un arbre n'a aucun cycle, donc aucun cycle impair : il est biparti, et une seule couleur ne suffit pas dès qu'il a une arête. Le piège, $6$, prend la borne $\Delta+1$ du glouton pour la valeur exacte.
Question 10 : Un graphe $G$ contient 4 sommets deux à deux voisins. Que peut-on affirmer ?
Réponse : C. Ces 4 sommets forment un $K_4$ : ils exigent déjà 4 couleurs, et le reste du graphe peut en demander plus. Le piège, $\chi(G)=4$, l'oublie : $K_5$ contient 4 sommets deux à deux voisins et demande 5 couleurs.
Question 11 : Chaque sommet d'un graphe a au plus 4 voisins. Quel que soit l'ordre, le glouton utilise :
Réponse : B. Quand vient son tour, un sommet a au plus 4 voisins déjà colorés : l'une des 5 premières couleurs reste libre. Le piège, $4$, est contredit par $K_5$ : chaque sommet y a 4 voisins, et le dernier colorié prend la cinquième couleur.
Question 12 : Que dit le théorème des quatre couleurs ?
Réponse : D. Il porte sur les graphes planaires, ceux qu'on dessine sans croisement d'arêtes. Le piège C change cette borne en valeur exacte, alors qu'un arbre, planaire, n'a besoin que de 2 couleurs.
Question 13 : Le glouton colore le chemin d'arêtes $ab$, $bc$, $cd$ dans l'ordre $a$, $d$, $b$, $c$. Combien de couleurs utilise-t-il ?
Réponse : A. $a$ et $d$ reçoivent 1, car $d$ n'a encore aucun voisin coloré ; $b$, voisin de $a$, reçoit 2 ; $c$, voisin de $b$ et de $d$, reçoit 3. Le piège B croit que le glouton trouve toujours $\chi$, qui vaut 2 pour cet arbre : son résultat dépend de l'ordre.
Question 14 : Un graphe $G$ ne contient aucun triangle (trois sommets deux à deux voisins). Que peut-on en déduire ?
Réponse : D. Le cycle $C_5$ n'a aucun triangle mais, impair, il lui faut 3 couleurs. Le piège A confond « sans triangle » et « sans cycle impair ». B est faux aussi : il existe des graphes sans triangle de nombre chromatique aussi grand qu'on veut (Diestel, théorème 5.2.5).
Question 15 : Un graphe a 6 sommets et 5 arêtes. Que peut-on affirmer ?
Réponse : B. Avec $n-1$ arêtes, connexe équivaut à arbre. Sans connexité, rien ne tient : un triangle et, à part, un chemin de 3 sommets font 6 sommets, 5 arêtes, un cycle et deux composantes. Le piège A oublie cette condition.
Sources
Programme d'informatique de MP2I et MPI, ministère de l'Enseignement supérieur, 2021 : texte officiel.
Programme de mathématiques expertes de terminale générale, Bulletin officiel de l'Éducation nationale : texte officiel.
Reinhard Diestel, Graph Theory, 6e édition, 2025, chapitres 1 et 5 : lecture libre.