O teorema de De Bruijn-Erdős na teoria dos grafos , demonstrado por Nicolaas Govert de Bruijn e Paul Erdős , estabelece que (para qualquer número natural k ) para um gráfico sem direção infinito ter uma coloração por k cores, é suficiente que 'este seja o caso para todos os seus subgráficos finitos. Em outras palavras: qualquer k -crítico (en) gráfico (ou seja, qualquer coloração que tenha pelo menos k cores, mas todos os subgráficos apropriados sejam k -1-coloríveis) tem um número finito de vértices.
A prova original de De Bruijn usava indução transfinita .
Gottschalk forneceu a seguinte evidência, muito curta, baseada no teorema da compactação de Tychonoff em topologia . Denote por K o conjunto de k cores e seja G = ( V , E ) um gráfico. De acordo com o teorema de Tychonoff, o espaço do produto X = K V de todos os mapeamentos de V a K é compacto . Para qualquer mapeamento f de uma parte de V para K , os elementos de X que coincidem com f nesta parte formam um fechado . Consequentemente, para qualquer subgrafo finito F de G , o conjunto X F dos elementos de X cuja restrição a F é uma k- coloração é fechado (por união finita). Se todos esses Fs são k- coloríveis, todos esses X F formam uma família de fechado tendo a propriedade de interseção finita (em) , ou seja, qualquer subfamília finita é de interseção não vazia. Por compactação a sua intersecção não estiver vazio , ou que intersecção não é outro senão todos os k -colorations de L .
Outra prova, a partir do lema de Zorn, foi dada por Lajos Pósa (in) , assim como a tese de doutorado de 1951, Gabriel Andrew Dirac . Se qualquer subgrafo finito de G é k -corável então, pelo Lema de Zorn, G é um gráfico parcial de um grafo máximo M para esta propriedade. A relação binária de não-adjacência em H é uma relação de equivalência cujas classes proporcionar um k -coloring de L . No entanto, esta prova é mais difícil de generalizar do que por compactação.
O teorema também pode ser demonstrado usando ultrafiltros ou análise não padronizada .
No caso especial em que V é contável , Crispin Nash-Williams fornece uma prova baseada no lema de König .
Todas as provas do teorema de De Bruijn-Erdős usam alguma forma do axioma da escolha . Isso é inevitável, porque há modelos de matemática que não verificam esse teorema (nem esse axioma).
Por exemplo, para k = 2, deixar L ser o gráfico cujos vértices são os números reais e em que dois números reais x e y são unidas por uma aresta quando | x - y | ± √ 2 é um número racional , ou seja, os vértices conectados a um real x são os reais da forma x ± ( √ 2 + q ) com q racional. Vamos definir nos vértices de G uma relação de equivalência por: dois vértices são equivalentes se sua diferença é a soma de um racional e um múltiplo da raiz quadrada de 2 por um inteiro par. Assim, em uma 2-coloração de G , dois vértices equivalentes devem ser da mesma cor. O gráfico formado pela contração de cada classe de equivalência em um único vértice forma um acoplamento infinito e pode ser facilmente bicolor usando o axioma de escolha. Portanto, qualquer subgrafo finito de G é bicolor. No entanto, podemos mostrar que em qualquer coloração de G , qualquer conjunto monocromático mensurável de Lebesgue é necessariamente de medida zero. Segue-se que no modelo de Solovay (in) (no qual qualquer conjunto de números reais é mensurável), G só pode ser colorido por uma infinidade de cores.
O teorema de De Bruijn-Erdős para gráficos contáveis é equivalente, em aritmética de segunda ordem , ao lema de König.
Uma aplicação do teorema de De Bruijn-Erdős diz respeito ao problema de Hadwiger-Nelson no número cromático do gráfico de unidade de distância do plano euclidiano (seus vértices são os pontos do plano e dois vértices são conectados por uma aresta quando sua distância euclidiana é 1). Alguns de seus subgráficos, como o fuso Moser , não podem ser coloridos com menos de 4 cores. O gráfico em si tem 7 cores, com base no mosaico hexagonal do plano. Portanto, o número cromático neste gráfico é um dos quatro inteiros 4, 5, 6 ou 7, mas não se sabe qual. O teorema de De Bruijn-Erdős mostra, entretanto, que existe um gráfico de unidade de distância finita cujo número cromático é o mesmo que o de todo o plano, portanto, se o último for estritamente maior que 4, esse fato pode ser demonstrado por um cálculo finito.
O teorema de De Bruijn-Erdős também pode ser usado para estender o teorema de Dilworth , em conjuntos (parcialmente) ordenados , do caso finito para o caso infinito. Este teorema estabelece que a largura de qualquer ordem finita (ou seja, o tamanho máximo de uma anticadeia ) é igual ao tamanho mínimo de uma partição em cadeias . Uma partição em cadeias pode ser interpretada como uma coloração do grafo de incomparabilidade da ordem (o grafo cujos vértices são os elementos do conjunto ordenado e as arestas conectam os pares de elementos não comparáveis). A partir dessa interpretação e do teorema de Dilworth, podemos demonstrar, graças ao teorema de De Bruijn-Erdős, que qualquer ordem infinita de largura menor ou igual a um inteiro w é uma união de w cadeias disjuntas.
Da mesma forma, o teorema de De Bruijn-Erdős torna possível estender o teorema das quatro cores , em grafos planares , do caso finito para o caso infinito: qualquer grafo planar infinito, ou mais geralmente qualquer grafo infinito cujos subgráficos finitos são planos, pode ser colorido por 4 cores.
Também pode ser usado para responder a uma pergunta de Fred Galvin (en) sobre um " teorema de valores intermediários para os números cromáticos de gráficos": para qualquer gráfico G de número cromático ke qualquer inteiro j <k , G tem um sub- gráfico de número cromático j . Para encontrar um, basta pegar um subgrafo finito de G de número cromático k e deletar um a um dos vértices até que o número cromático do subgráfico alcance o valor j . No entanto, a situação para os números cromáticos infinitos é mais complicada: a teoria dos conjuntos é consistente com a existência de um gráfico de número cromático (e número de vértices) igual a ℵ 2 , sem subgrafo numérico. Cromático igual a ℵ 1 .
Richard Rado (em 1949) demonstrou o seguinte teorema, que generaliza e esclarece o de De Bruijn-Erdős. Seja V um conjunto infinito e, para cada elemento v de V , um conjunto finito c v de cores. Escolhemos, para qualquer parte finita S de V , um mapa C S de S no conjunto de cores, de forma que a cor de cada elemento v de S pertença a c v . Então existe um mapa χ , definido em V inteiro, tal que qualquer parte finita S está incluída em uma parte finita T na qual χ e C T coincidem.
Se o número cromático de um gráfico G é infinito, então, o teorema de De Bruijn-Erdős implica que G contém, para qualquer inteiro j , um subgrafo cujo número cromático é j (cf. teorema do valor intermediário acima ). Os pesquisadores também examinaram outras consequências nos subgráficos de G ; por exemplo, G também deve conter qualquer grafo bipartido finito como um subgrafo. No entanto, G pode ter uma célula ímpar arbitrariamente grande e, portanto, para qualquer conjunto finito de grafos não bipartidos , existe um G do qual nenhum subgrafo pertence a este conjunto.
O teorema de De Bruijn-Erdős também se aplica diretamente aos problemas de coloração de hipergrafos , onde pedimos que para cada hiper-aresta, os vértices não sejam todos da mesma cor: como para gráficos, um hipergrafo é k -colorível se e somente se cada um de seus sub-hipergrafos finitos é. Este é um caso especial do teorema de compactação de Gõdel , em que um conjunto de declarações de primeira ordem tem um modelo quando cada uma de suas partes acabadas por a.
Também podemos generalizar o teorema para situações em que o número de cores é um cardinal infinito: se κ for um cardinal fortemente compacto (in) então, para qualquer gráfico G e qualquer cardinal μ <κ, o número cromático de G é menor que ou igual a μ se e somente se o mesmo for verdadeiro para cada um de seus subgráficos com uma cardinalidade estritamente menor que κ. O teorema de De Bruijn-Erdős original é o caso κ = ℵ 0 desta generalização. Mas isso requer uma hipótese como a de forte compactação de κ: sob a hipótese do contínuo generalizado , para qualquer cardinal infinito γ , existe um gráfico G de cardinal (2 γ ) + cujo número cromático é estritamente maior que γ , mas todos os subgráficos que são estritamente menores (em número de vértices) que o gráfico têm um número cromático menor ou igual a γ . Lake caracteriza gráficos infinitos para os quais a generalização do teorema de De Bruijn-Erdős é verdadeira, no sentido de que seu número cromático é igual ao máximo dos números cromáticos de seus subgráficos estritamente menores.