Théorème de De Bruijn-Erdős (théorie des graphes)

Si tout sous-graphe fini est 3-coloriable, alors le graphe est 3-coloriable.

Le théorème de De Bruijn-Erdős en théorie des graphes, démontré par Nicolaas Govert de Bruijn et Paul Erdős, établit que (pour tout entier naturel k) pour qu'un graphe non orienté infini possède une coloration par k couleurs, il suffit qu'il en soit ainsi pour tous ses sous-graphes finis. Autrement dit : tout graphe k-critique (en) (i.e. dont toute coloration a au moins k couleurs mais dont tous les sous-graphes propres sont k – 1-colorables) a un nombre fini de sommets.

Démonstrations

La preuve originelle de De Bruijn utilisait l'induction transfinie.

Gottschalk a fourni la preuve suivante, très courte, basée sur le théorème de compacité de Tychonoff en topologie. Notons K l'ensemble des k couleurs et soit G = (V, E) un graphe. D'après le théorème de Tychonoff, l'espace produit X = K^V de toutes les applications de V dans K est compact. Pour toute application f d'une partie de V dans K, les éléments de X qui coïncident avec f sur cette partie forment un fermé. Par conséquent, pour tout sous-graphe fini F de G, l'ensemble X_F des éléments de X dont la restriction à F est une k-coloration est fermé (par réunion finie). Si tous ces F sont k-colorables, tous ces X_F forment une famille de fermés ayant la propriété d'intersection finie (en), c'est-à-dire que toute sous-famille finie est d'intersection non vide. Par compacité leur intersection est donc non vide, or cette intersection n'est autre que l'ensemble des k-colorations de G.

Une preuve différente, utilisant le lemme de Zorn, a été donnée par Lajos Pósa (en), ainsi que dans la thèse de Ph.D. de 1951 de Gabriel Andrew Dirac. Si tout sous-graphe fini de G est k-colorable alors, d'après le lemme de Zorn, G est un graphe partiel d'un graphe M maximal pour cette propriété. La relation binaire de non-adjacence dans M est une relation d'équivalence dont les classes fournissent une k-coloration de G. Cependant, cette preuve est plus difficile à généraliser que celle par compacité.

Le théorème peut aussi se démontrer en utilisant les ultrafiltres ou l'analyse non standard.

Dans le cas particulier où V est dénombrable, Crispin Nash-Williams donne une preuve basée sur le lemme de König.

Rôle de l'axiome du choix

Toutes les démonstrations du théorème de De Bruijn-Erdős utilisent une forme ou une autre de l'axiome du choix. Cela est inévitable, car il existe des modèles des mathématiques ne vérifiant pas ce théorème (ni cet axiome).

Par exemple pour k = 2, soit G le graphe dont les sommets sont les nombres réels et dans lequel deux réels x et y sont joints par une arête lorsque |x – y| ± √2 est un nombre rationnel, c'est-à-dire que les sommets reliés à un réel x sont les réels de la forme x ± (√2 + q) avec q rationnel. Définissons sur les sommets de G une relation d'équivalence par : deux sommets sont équivalents si leur différence est somme d'un rationnel et d'un multiple de racine carrée de 2 par un entier pair. Ainsi, dans une 2-coloration de G, deux sommets équivalents doivent être de la même couleur. Le graphe formé en contractant chaque classe d'équivalence en un unique sommet forme alors un couplage infini et peut facilement être 2-coloré en utilisant l'axiome du choix. Par conséquent, tout sous-graphe fini de G est 2-colorable. Cependant, on peut montrer que dans toute coloration de G, tout ensemble Lebesgue-mesurable monochrome est nécessairement de mesure nulle. Il en résulte que dans le modèle de Solovay (en) (dans lequel tout ensemble de réels est mesurable), G n'est colorable que par une infinité de couleurs.

Le théorème de De Bruijn-Erdős pour les graphes dénombrables est équivalent, dans l'arithmétique du second ordre, au lemme de König.

Applications

Une 7-coloration du plan et un graphe distance-unité de nombre chromatique égal à 4 fournissent un majorant et un minorant pour le problème de Hadwiger-Nelson.

Une application du théorème de De Bruijn-Erdős concerne le problème de Hadwiger-Nelson sur le nombre chromatique du graphe distance-unité du plan euclidien (ses sommets sont les points du plan et deux sommets sont reliés par une arête lorsque leur distance euclidienne vaut 1). Certains de ses sous-graphes, comme le fuseau de Moser, ne sont pas colorables par moins de 4 couleurs. Le graphe lui-même possède une 7-coloration, basée sur le pavage hexagonal du plan. Par conséquent, le nombre chromatique de ce graphe est l'un des quatre entiers 4, 5, 6 ou 7, mais on ne sait pas lequel. Le théorème de De Bruijn-Erdős montre cependant qu'il existe un graphe distance-unité fini dont le nombre chromatique est le même que celui du plan tout entier, donc si ce dernier est strictement plus grand que 4 alors ce fait peut être démontré par un calcul fini.

Le théorème de De Bruijn-Erdős peut aussi être utilisé pour étendre le théorème de Dilworth, sur les ensembles (partiellement) ordonnés, du cas fini au cas infini. Ce théorème établit que la largeur de tout ordre fini (i.e. la taille maximum d'une antichaîne) est égale à la taille minimum d'une partition en chaînes. Une partition en chaînes peut s'interpréter comme une coloration du graphe d'incomparabilité de l'ordre (le graphe dont les sommets sont les éléments de l'ensemble ordonné et les arêtes relient les paires d'éléments non comparables). À partir de cette interprétation et au théorème de Dilworth, on peut démontrer, grâce au théorème de De Bruijn-Erdős, que tout ordre infini de largeur inférieure ou égale à un entier w est réunion de w chaînes disjointes.

De même, le théorème de De Bruijn-Erdős permet d'étendre le théorème des quatre couleurs, sur les graphes planaires, du cas fini au cas infini : tout graphe planaire infini, ou plus généralement tout graphe infini dont les sous-graphes finis sont planaires, peut être coloré par 4 couleurs.

Il peut aussi servir à répondre à une question de Fred Galvin sur un « théorème des valeurs intermédiaires pour les nombres chromatiques de graphes » : pour tout graphe G de nombre chromatique k et tout entier j < k, G possède un sous-graphe de nombre chromatique j. Pour en trouver un, il suffit de prendre un sous-graphe fini de G de nombre chromatique k et de supprimer un par un des sommets jusqu'à ce que le nombre chromatique du sous-graphe atteigne la valeur j. Cependant, la situation pour des nombres chromatiques infinis est plus compliquée : la théorie des ensembles est consistante avec l'existence d'un graphe de nombre chromatique (et nombre de sommets) égal à ℵ₂, n'ayant aucun sous-graphe de nombre chromatique égal à ℵ₁.

Généralisations

Richard Rado (en 1949) a démontré le théorème suivant, qui généralise et précise celui de De Bruijn-Erdős. Soient V un ensemble infini et, pour chaque élément v de V, un ensemble fini c_v de couleurs. On choisit, pour toute partie finie S de V, une application C_S de S dans l'ensemble des couleurs, telle que la couleur de chaque élément v de S appartienne à c_v. Alors il existe une application χ, définie sur V tout entier, telle que toute partie finie S soit incluse dans une partie finie T sur laquelle χ et C_T coïncident.

Si le nombre chromatique d'un graphe G est infini alors, le théorème de De Bruijn-Erdős implique que G contient, pour tout entier j, un sous-graphe dont le nombre chromatique est j (cf. théorème des valeurs intermédiaires ci-dessus). Des chercheurs ont aussi examiné d'autres conséquences sur les sous-graphes de G ; par exemple, G doit aussi contenir tout graphe biparti fini comme sous-graphe. Cependant, G peut avoir une maille impaire arbitrairement grande et, par conséquent, pour tout ensemble fini de graphes non bipartis, il existe un G dont aucun sous-graphe n'appartient à cet ensemble.

Le théorème de De Bruijn-Erdős s'applique aussi directement aux problèmes de coloration d'hypergraphes, où l'on demande que pour chaque hyperarête, les sommets ne soient pas tous de la même couleur : comme pour les graphes, un hypergraphe est k-colorable si et seulement si chacun de ses sous-hypergraphes finis l'est. C'est un cas particulier du théorème de compacité de Gödel, selon lequel un ensemble d'énoncés du premier ordre a un modèle dès que chacune de ses parties finies en a.

On peut aussi généraliser le théorème à des situations où le nombre de couleurs est un cardinal infini : si κ est un cardinal fortement compact (en) alors, pour tout graphe G et tout cardinal μ < κ, le nombre chromatique de G est inférieur ou égal à μ si et seulement s'il en est de même pour chacun de ses sous-graphes de cardinal strictement inférieur à κ. Le théorème originel de De Bruijn-Erdős est le cas κ = ℵ₀ de cette généralisation. Mais celle-ci nécessite une hypothèse comme celle de compacité forte de κ : sous l'hypothèse généralisée du continu, pour tout cardinal infini γ, il existe un graphe G de cardinal (2^γ)⁺ dont le nombre chromatique est strictement supérieur à γ, mais dont tous les sous-graphes strictement plus petits (en nombre de sommets) que le graphe ont un nombre chromatique inférieur ou égal à γ. Lake caractérise les graphes infinis pour lesquels la généralisation du théorème de De Bruijn-Erdős est vraie, au sens où leur nombre chromatique est égal au maximum des nombres chromatiques de leurs sous-graphes strictement plus petits.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « De Bruijn–Erdős theorem (graph theory) » (voir la liste des auteurs).