En teoria de grafs, el teorema de De Bruijn–Erdős relaciona la coloració de grafs d'un graf infinit amb el mateix problema dels seus subgrafs finits. Afirma que, quan es poden acolorir tots els subgrafs finits amb  colors, el mateix passa amb tot el graf. El teorema va ser demostrat per Nicolaas de Bruijn i Paul Erdős (1951), dels quals rep el nom.

El teorema de De Bruijn–Erdős té diverses demostracions diferents, totes depenent d'alguna manera de l'axioma de l'elecció. Les seves aplicacions inclouen estendre el teorema dels quatre colors i el teorema de Dilworth de grafs finits i conjunts parcialment ordenats a infinits, i reduir el problema de Hadwiger-Nelson sobre el nombre cromàtic del pla a un problema sobre gràfics finits. Es pot generalitzar des de nombres finits de colors fins a conjunts de colors la cardinalitat dels quals és un cardinal fortament compacte.

Definicions i enunciat Un graf no dirigit és un objecte matemàtic format per un conjunt de vèrtexs i un conjunt d'arestes que enllacen parells de vèrtexs. Els dos vèrtexs associats a cada aresta s'anomenen «extrems». El graf és finit quan els seus vèrtexs i arestes formen conjunts finits, i infinits en cas contrari. Una coloració de grafs associa cada vèrtex amb un color extret d'un conjunt de colors, de manera que cada aresta té dos colors diferents als seus extrems. Un objectiu freqüent en la coloració de gràfics és minimitzar el nombre total de colors que s'utilitzen; el «nombre cromàtic» d'un graf és aquest nombre mínim de colors.Per a aquestes definicions bàsiques, vegeu [Jensen, Toft 1995, p. 1-2] El teorema dels quatre colors estableix que cada graf finit que es pot dibuixar sense encreuaments en el pla euclidià necessita com a màxim quatre colors; tanmateix, alguns grafs amb connectivitat més complicada requereixen més de quatre colors. És una conseqüència de l'axioma de l'elecció que el nombre cromàtic està ben definit per a grafs infinits, però per a aquests grafs el nombre cromàtic podria ser en si mateix un nombre cardinal infinit.

Un subgraf d'un graf és un altre graf obtingut a partir d'un subconjunt dels seus vèrtexs i d'un subconjunt de les seves arestes. Si el graf més gran està acolorit, es pot utilitzar el mateix color per al subgraf. Per tant, el nombre cromàtic d'un subgraf no pot ser més gran que el nombre cromàtic de tot el graf. El teorema de De Bruijn-Erdős es refereix als nombres cromàtics de grafs infinits, i mostra que (de nou, assumint l'axioma de l'elecció) es poden calcular a partir dels nombres cromàtics dels seus subgrafs finits. Afirma que, si els nombres cromàtics dels subgrafs finits d'un graf  tenen un valor màxim finit , el nombre cromàtic de és exactament . D'altra banda, si no hi ha cap límit superior finit en els nombres cromàtics dels subgrafs finits de , el nombre cromàtic de ha de ser infinit.

Aplicacions La motivació original d'Erdős a l'hora d'estudiar aquest problema va ser estendre dels grafs finits a infinits el teorema que, sempre que un graf tingui una orientació amb un grau superior finit, també té una -coloració. Per als grafs finits això succeeix perquè aquests grafs sempre tenen un vèrtex de grau com a màxim, que es pot acolorir amb un de colors després que tots els vèrtexs restants s'acoloreixin de manera recursiva. Els grafs infinits amb aquesta orientació no sempre tenen un vèrtex de baix grau (per exemple, les xarxes de Bethe tenen , però un grau mínim arbitràriament gran), de manera que aquest argument requereix que el graf sigui finit. Però el teorema de De Bruijn-Erdős mostra que existeix una -coloració fins i tot per a grafs infinits.[Erdős 1950], en particular a la pàgina 137, on el teorema de De Bruijn-Erdős s'anuncia per primera vegada (però no demostrat) amb una pista que el lema de Kőnig es pot utilitzar per a grafs comptables.

miniatura|Un pla de set colors i el graf de Moser de quatre cromàtics dibuixats com a graf de distància unitat en el pla, proporcionant límits superiors i inferiors per al problema de Hadwiger-Nelson Una altra aplicació del teorema de De Bruijn-Erdős és al problema de Hadwiger-Nelson, que pregunta quants colors es necessiten per acolorir els punts del pla euclidià de manera que cada dos punts que es troben a una distància unitat tinguin colors diferents. Aquest és un problema de coloració de grafs per a un graf infinit que té un vèrtex per a cada punt del pla i una aresta per cada dos punts la distància euclidiana dels quals és exactament una. Els subgrafs d'aquest grafs s'anomenen «grafs de distància unitat». Un graf de distància unitat de set vèrtex, el graf de Moser, requereix quatre colors; el 2018, es van trobar grafs de distància d'unitats molt més grans que requereixen cinc colors. Tot el graf infinit té una coloració coneguda amb set colors basat en un mosaic hexagonal del pla. Per tant, el nombre cromàtic del pla ha de ser 5, 6 o 7, però no se sap quin d'aquests tres nombres és el valor correcte. El teorema de De Bruijn-Erdős mostra que, per a aquest problema, existeix un graf de distància unitat finita amb el mateix nombre cromàtic que tot el pla, de manera que si el nombre cromàtic és superior a cinc, aquest fet es pot demostrar mitjançant un càlcul finit.

El teorema de De Bruijn-Erdős també es pot utilitzar per estendre el teorema de Dilworth de conjunts parcialment ordenats finits a infinits. El teorema de Dilworth estableix que l'amplada d'un ordre parcial (el nombre màxim d'elements en un conjunt d'elements mútuament incomparables) és igual al nombre mínim de cadenes (subconjunts totalment ordenats) en què es pot dividir l'ordre parcial. Una partició en cadenes es pot interpretar com una coloració del graf d'incomparabilitat de l'ordre parcial. Aquest és un graf amb un vèrtex per a cada element de l'ordre i una aresta per a cada parell d'elements incomparables. Utilitzant aquesta interpretació de color, juntament amb una demostració separada del teorema de Dilworth per a conjunts parcialment ordenats finits, és possible demostrar que un conjunt parcialment ordenat infinit té una amplada finita  si i només si té una partició en cadenes.

De la mateixa manera, el teorema de De Bruijn-Erdős amplia el teorema dels quatre colors des de grafs planars finits fins a grafs planars infinits. Cada graf pla finit es pot pintar amb quatre colors, segons el teorema dels quatre colors. Aleshores, el teorema de De Bruijn-Erdős mostra que cada graf que es pot dibuixar sense encreuaments en el pla, finit o infinit, es pot pintar amb quatre colors. De manera més general, cada graf infinit per al qual tots els subgrafs finits són plans pot tornar a ser de quatre colors.[Nash-Williams 1967] afirma el mateix resultat per al teorema dels cinc colors per als gràfs planars comptables, ja que el teorema dels quatre colors encara no s'havia demostrat quan va publicar la seva investigació, i com que la demostració del teorema de De Bruijn-Erdős que dona només s'aplica als grafs comptables. Per a la generalització a gràfs en què cada subgraf finit és pla (provat directament mitjançant el teorema de compacitat de Gödel). Vegeu [Rautenberg 2010].

Demostracions La demostració original del teorema de De Bruijn-Erdős, de De Bruijn, utilitzava la inducció transfinita.

[Gottschalk 1951] va proporcionar la següent demostració molt breu, basada en el teorema de compacitat de Tíkhonov en topologia. Suposem que, per al graf infinit donat , cada subgraf finit és -colorable, i fem que  sigui l'espai de totes les tasques dels -colors als vèrtexs de  (independentment de si formen una coloració vàlida). Aleshores es pot donar una topologia com a espai de producte , on  denota el conjunt de vèrtexs del graf. Segons el teorema de Tychonoff, aquest espai topològic és compacte. Per a cada subgraf finit de , fem que sigui el subconjunt de  consistent en assignacions de colors que acoloreixin vàlidament . Llavors, el sistema de conjunts és una família de conjunts tancats amb la propietat de la intersecció finita, de manera que per compacitat té una intersecció no buida. Cada membre d'aquesta intersecció és un color vàlid de .Gottschalk afirma la seva demostració de manera més general com una demostració del teorema de [Rado 1949] que generalitza el teorema de De Bruijn–Erdős.

Una prova diferent utilitzant el lema de Zorn va ser donada per Lajos Pósa, i també en la tesi doctoral Ph.D. de 1951 de Gabriel Andrew Dirac. Si  és un graf infinit en el qual es troba cada subgraf finit -colorable, llavors pel lema de Zorn és un subgraf d'un graf màxim  amb la mateixa propietat (una a la qual no es poden afegir més arestes sense fer que algun subgraf finit requereixi més de  colors). La relació binària de no adjacència en  és una relació d'equivalència i les seves classes d'equivalència proporcionen una -coloració de . Tanmateix, aquesta demostració és més difícil de generalitzar que la prova de compacitat.[Jensen, Toft 1995] atribueixen a Gert Sabidussi l'observació que la demostració de Gottschalk és més fàcil de generalitzar. [Soifer 2008, pàg. 238-239] dona la mateixa prova mitjançant el lema de Zorn, redescobert el 2005 per l'estudiant de grau Dmytro Karabash.

El teorema també es pot demostrar mitjançant ultrafiltres o anàlisis no estàndard. Dona una demostració per a grafs amb un nombre comptable de vèrtexs basat en el lema de l'infinit de Kőnig.

Dependència de l'elecció Totes les demostracions del teorema de De Bruijn-Erdős utilitzen alguna forma de l'axioma de l'elecció. És necessària alguna forma d'aquesta suposició, ja que existeixen models de matemàtiques en què tant l'axioma de l'elecció com el teorema de De Bruijn-Erdős són falsos. Més precisament, [Mycielski 1961] va demostrar que el teorema és una conseqüència del teorema de l'ideal primer booleà, una propietat que està implicada per l'axioma de l'elecció però més feble que l'axioma complet de l'elecció, i [Läuchli 1971] va demostrar que el teorema de De Bruijn-Erdős i el teorema de l'ideal primer booleà són equivalents en potència axiomàtica.Per a aquesta història, vegeu [Cowen Hechler Mihók, 2002]. Per a la demostració simplificada del teorema de Läuchli per Mycielski, vegeu [Cowen 1990].

També es pot demostrar que el teorema de De Bruijn-Erdős per a grafs comptables és equivalent en poder axiomàtic, dins d'una teoria de l'aritmètica de segon ordre, al lema de l'infinit de Kőnig.

Per a un contraexemple del teorema en models de teoria de conjunts sense elecció, fem que sigui un graf infinit en què els vèrtexs representen tots els nombres reals possibles. En , es connecta cada dos nombres reals  i per una vora sempre que un dels valors  és un nombre racional. De manera equivalent, en aquest graf existeixen arestes entre tots els nombres reals  i tots els nombres reals de la forma , per a nombres racionals . Cada camí d'aquest graf, començant per qualsevol nombre real , alterna números que difereixen de  per un nombre racional més un múltiple parell de  i números que difereixen de  per un nombre racional més un múltiple senar de .

Aquesta alternança evita que contingui qualsevol cicle de longitud senar, de manera que cadascun dels seus subgrafs finits només requereix dos colors. Tanmateix, en el model de Solovay en què cada conjunt de nombres reals és mesurable per Lebesgue, requereix infinits colors, ja que en aquest cas cada classe de color ha de ser un conjunt mesurable i es pot demostrar que cada conjunt mesurable de nombres reals sense arestes en  ha de tenir la mesura zero. Per tant, en el model de Solovay, el nombre cromàtic (infinit) de tots  és molt més gran que el nombre cromàtic dels seus subgrafs finits (com a màxim dos).

Generalitzacions