vignette|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 (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 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 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 forment une famille de fermés ayant la , 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. prouve le théorème de De Bruijn-Erdős en redémontrant un théorème plus général de Richard Rado : ..

Une preuve différente, utilisant le lemme de Zorn, a été donnée par , 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é. attribuent à la remarque que la preuve de Gottschalk est plus facile à généraliser. donne la même preuve par le lemme de Zorn, redécouverte en 2005 par l'étudiant de premier cycle Dmytro Karabash..

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| ± est un nombre rationnel, c'est-à-dire que les sommets reliés à un réel x sont les réels de la forme x ± ( + 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 (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 vignette|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. établit ce résultat seulement pour 5 couleurs – le théorème des 4 couleurs n'était pas encore démontré lors de cette publication – et pour des graphes planaires dénombrables – la preuve du théorème de De Bruijn-Erdős qu'il donne ne s'applique qu'à ce cas. Pour la généralisation aux graphes dont tout sous-graphe fini est planaire (démontrée directement via le théorème de compacité de Gödel), voir ..

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 a démontré le théorème suivant, qui généralise et précise celui de De Bruijn-ErdősPour ce lien entre le théorème de Rado et celui de De Bruijn-Erdős, voir par exemple la discussion qui suit Theorem A dans .. Soient V un ensemble infini et, pour chaque élément v de V, un ensemble fini c de couleurs. On choisit, pour toute partie finie S de V, une application C de S dans l'ensemble des couleurs, telle que la couleur de chaque élément v de S appartienne à c. 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 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 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 à κCeci résulte immédiatement de la définition de la compacité forte du cardinal κ : un ensemble de formules de la logique infinitaire dont chacune est de longueur strictement inférieure à κ est satisfaisable dès que toutes ses parties de cardinal strictement inférieur à κ le sont. Voir par exemple .. 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

De Bruijn-Erdos Catégorie:Théorie des ensembles Catégorie:Coloration d'un graphe