théorème de Brooks

Imaginez des points reliés par des traits. Deux points reliés doivent recevoir des couleurs différentes. Si chaque point touche au plus trois autres points, combien de couleurs faut-il prévoir ? Le théorème de Brooks répond que trois suffisent, sauf pour deux formes très particulières.

La force du résultat vient de ce gain d’une couleur : la règle générale en autorise quatre, tandis que la structure du graphe permet souvent de revenir à trois.

Une coloration propre des sommets attribue une couleur à chaque sommet d’un graphe sans donner la même couleur à deux sommets reliés par une arête. Le nombre chromatique, noté par la lettre grecque χ appliquée au graphe G, est le plus petit nombre de couleurs permettant une telle coloration. Le degré maximal, noté Δ, est le plus grand nombre de voisins rencontré parmi les sommets.

Le théorème de Brooks concerne un graphe G simple, connexe et non orienté. Hors exceptions, sa conclusion s’écrit $\chi (G)\le \mathrm{\Delta }\backslash chi(G)\backslash leq\backslash Delta$ : le degré maximal fournit donc une borne supérieure du nombre chromatique. Il ne prétend pas que toutes les couleurs disponibles seront nécessaires.

Dans ce cadre de graphes simples, les exceptions sont les graphes complets K_n, dans lesquels chaque paire de sommets est reliée, et les cycles de longueur impaire. Pour ces graphes, il faut Δ + 1 couleurs. Démontré en 1941 par le mathématicien britannique R. Leonard Brooks, le résultat resserre ainsi d’une unité la borne générale Δ + 1 dès que le graphe n’appartient pas à ces familles.

Soit G un graphe simple, connexe et non orienté, et soit Δ son degré maximal. Si G n’est ni un graphe complet ni un cycle de longueur impaire, alors son nombre chromatique vérifie $\chi (G)\le \mathrm{\Delta }\backslash chi(G)\backslash leq\backslash Delta$.

Dans ce même cadre de graphes simples, si G est complet ou s’il s’agit d’un cycle impair, la valeur devient $\chi (G)=\mathrm{\Delta }+1\backslash chi(G)=\backslash Delta+1$. Il faut donc identifier ces deux formes avant d’appliquer la borne améliorée.

Le graphe doit être simple, c’est-à-dire sans boucle ni arête multiple, et non orienté : une arête traduit un voisinage réciproque. Il doit aussi être connexe, c’est-à-dire qu’un chemin relie toute paire de sommets. Enfin, Δ se calcule sur tous les sommets avant de chercher la coloration. Ces données permettent d’obtenir une borne sur le nombre minimal de couleurs.

Un graphe complet à quatre sommets fournit un contre-cas concret : chaque sommet a trois voisins, mais trois couleurs ne suffisent pas puisque tous les sommets sont voisins deux à deux. Il faut alors utiliser la règle exceptionnelle, qui donne quatre couleurs. Si un graphe est non connexe, on examine séparément chacune de ses composantes connexes.

Considérons le graphe du prisme triangulaire. Ses sommets sont A, B, C, D, E et F. Ses arêtes forment les triangles ABC et DEF, auxquels s’ajoutent AD, BE et CF.

1. Chaque sommet a exactement trois voisins ; le degré maximal vaut donc Δ = 3.
2. Le graphe est connexe, non orienté, et il n’est pas complet.
3. Ce n’est pas un cycle impair : chaque sommet a degré 3, alors que les sommets d’un cycle ont degré 2. Le théorème autorise donc au plus trois couleurs.

4. Attribuons la première couleur à A et F, la deuxième à B et D, puis la troisième à C et E. Sur chacune des neuf arêtes annoncées, les extrémités ont des couleurs différentes.

Le triangle ABC impose au moins trois couleurs, car ses trois sommets sont voisins deux à deux. La coloration construite en utilise trois : le nombre chromatique du prisme vaut donc exactement χ = 3, en accord avec la borne de Brooks.

Pour majorer rapidement le nombre chromatique, on calcule d’abord le degré maximal. Si le graphe est connexe et n’appartient à aucune famille exceptionnelle, la borne de Brooks remplace la borne générale Δ + 1 par Δ.

Pour montrer que la borne est exacte, il faut ensuite chercher une obstruction qui impose autant de couleurs. Dans le prisme triangulaire, le triangle ABC impose trois couleurs ; la coloration explicite prouve qu’une quatrième serait inutile.

Pour contrôler une coloration proposée, on inspecte chaque arête et l’on vérifie que ses deux extrémités diffèrent. Cette vérification établit une borne supérieure, mais seule une obstruction séparée établit qu’aucune coloration plus économe n’existe.

Le théorème de Brooks ne se confond pas avec la borne générale Δ + 1. La borne générale vaut pour n’importe quel graphe, tandis que Brooks retire une couleur sous ses hypothèses, sauf pour les graphes complets et les cycles impairs. Un graphe complet à quatre sommets tranche nettement : sa valeur est 4, et non 3.

Une borne supérieure ne se confond pas non plus avec la valeur exacte du nombre chromatique. Si Δ vaut 3, Brooks garantit au plus trois couleurs dans le cas ordinaire ; le graphe peut parfois en demander moins. Pour prouver l’égalité, il faut ajouter un argument de minimalité, comme le triangle dans le prisme.

Dans un graphe complet K_n, tous les sommets sont voisins deux à deux. Le symptôme est immédiat : aucune couleur ne peut être réutilisée. Il faut employer Δ + 1 couleurs plutôt que la borne Δ.

Dans un cycle de longueur impaire, deux couleurs alternées finissent par attribuer la même couleur aux extrémités de la dernière arête. Comme Δ = 2, ce cas charnière demande trois couleurs, soit Δ + 1. Un cycle de longueur paire, lui, n’est pas une exception.

Le mot « au plus » est essentiel. La conclusion χ ≤ Δ n’annonce pas automatiquement χ = Δ. Il faut construire une coloration pour obtenir une borne supérieure, puis fournir séparément une raison interdisant toute coloration avec moins de couleurs si l’on revendique l’égalité.

La connexité appartient à l’énoncé fourni. Si plusieurs composantes sont présentes, appliquer aveuglément la phrase à l’ensemble masque leur structure ; il faut traiter chaque composante connexe, puis retenir le plus grand nombre de couleurs requis.

La fiche coloration d'un graphe replace le théorème dans le problème général : construire une coloration propre et déterminer combien de couleurs sont nécessaires.

Une piste naturelle consiste ensuite à comparer deux preuves distinctes : une coloration explicite donne une borne supérieure, tandis qu’un sous-graphe complet ou un cycle impair peut imposer une borne inférieure. Lorsque les deux nombres coïncident, le nombre chromatique est déterminé.