En teoría de grafos, el teorema de De Bruijn-Erdős relaciona la coloración de un grafo infinito con el mismo problema en sus subgrafos finitos. Establece que, cuando todos los subgrafos finitos pueden colorearse con colores, lo mismo ocurre con todo el grafo. El teorema fue demostrado por Nicolaas Govert de Bruijn y Paul Erdős (1951), de quienes recibe su nombre.

El teorema de De Bruijn-Erdős tiene varias demostraciones diferentes, todas dependientes de alguna manera del axioma de elección. Sus aplicaciones incluyen la extensión del teorema de los cuatro colores y del teorema de Dilworth de grafos finitos y conjuntos parcialmente ordenados a grafos infinitos, y la reducción del problema de Hadwiger-Nelson de la coloración de grafos del plano a un problema sobre grafos finitos. Puede generalizarse de un número finito de colores a conjuntos de colores cuya cardinalidad es un cardinal fuertemente compacto.

Definiciones y enunciado Un grafo es un objeto matemático que consiste en un conjunto de vértices y un conjunto de aristas que enlazan pares de vértices. Los dos vértices asociados a cada arista se denominan extremos. El grafo es finito cuando sus vértices y aristas forman un conjunto finito, e infinito en caso contrario. Una coloración de grafos asocia cada vértice con un color extraído de un conjunto de colores, de tal manera que cada arista tiene dos colores diferentes en sus extremos. Un objetivo frecuente en la coloración de grafos es minimizar el número total de colores utilizados. La coloración de un grafo es este número mínimo de colores.Para estas definiciones básicas, véase , pp. 1–2. El teorema de los cuatro colores establece que todo grafo finito que pueda dibujarse sin cruces en el plano necesita como máximo cuatro colores. Sin embargo, algunos grafos con conectividad más compleja requieren más de cuatro colores., p. 5. Es una consecuencia del axioma de elección que el número de colores esté bien definido para grafos infinitos, pero para estos grafos el número cromático podría ser en sí mismo un número cardinal infinito.

Un subgrafo de un grafo es otro grafo obtenido a partir de un subconjunto de sus vértices y un subconjunto de sus aristas. Si el grafo mayor está coloreado, se puede usar la misma coloración para el subgrafo. Por lo tanto, el número cromático de un subgrafo no puede ser mayor que el número cromático del grafo completo. El teorema de De Bruijn-Erdős se refiere a los números cromáticos de grafos infinitos y demuestra que (de nuevo, asumiendo el axioma de elección) pueden calcularse a partir de los números cromáticos de sus subgrafos finitos. Afirma que, si los números cromáticos de los subgrafos finitos de un grafo tienen un valor máximo finito , entonces el número cromático de es exactamente . Por otro lado, si no hay ningún límite superior finito en los números cromáticos de los subgrafos finitos de , entonces el número cromático de debe ser infinito., Theorem 1, p. 2.

Aplicaciones La motivación original de Erdős al estudiar este problema fue extender de grafos finitos a infinitos el teorema que establece que, siempre que un grafo tenga una orientación con un grado de salida máximo finito , también tendrá una coloración . Para grafos finitos, esto se deduce porque dichos grafos siempre tienen un vértice de grado máximo , que puede colorearse con uno de los colores después de colorear recursivamente todos los vértices restantes. Los grafos infinitos con dicha orientación no siempre tienen un vértice de grado bajo (por ejemplo, los retículos de Bethe tienen , pero un grado mínimo arbitrario), por lo que este argumento requiere que el grafo sea finito. Sin embargo, el teorema de De Bruijn-Erdős muestra que existe una coloración con colores incluso para grafos infinitos.. Véase en particular p. 137, donde el teorema De Bruijn–Erdős es enunciado por primera vez (aunque no probado), con una pista de que el lema de Kőnig se puede utilizar para gráficos numerables.

Otra aplicación del teorema de De Bruijn-Erdős es al problema de Hadwiger-Nelson, que pregunta cuántos colores se necesitan para colorear los puntos del plano de modo que cada dos puntos separados por una unidad de distancia tengan colores diferentes. Este es un problema de coloración de grafos para un grafo infinito que tiene un vértice por cada punto del plano y una arista por cada dos puntos cuya distancia euclídea es exactamente uno. Los subgrafos inducidos de este grafo se llaman grafos de distancia unitaria. Un grafo de distancia unitaria de siete vértices, el huso de Moser, requiere cuatro colores. En 2018, se encontraron grafos de distancia unitaria mucho mayores que requieren cinco colores. Todo el grafo infinito tiene una coloración conocida con siete colores basada en una teselación hexagonal del plano. Por lo tanto, el número cromático del plano debe ser 5, 6 o 7, pero se desconoce cuál de estos tres números es el valor correcto. El teorema de De Bruijn-Erdős muestra que, para este problema, existe un grafo de distancia unitaria finito con el mismo número cromático que todo el plano. Por lo tanto, si el número cromático es mayor que cinco, este hecho puede demostrarse mediante un cálculo finito.

El teorema de De Bruijn-Erdős también puede usarse para extender el teorema de Dilworth de conjuntos parcialmente ordenados finitos a infinitos. El teorema de Dilworth establece que la anchura de un orden parcial (el número máximo de elementos en un conjunto de elementos mutuamente incomparables) es igual a la cantidad mínima de cadenas (subconjuntos totalmente ordenados) en las que puede dividirse el orden parcial. Una partición en cadenas puede interpretarse como una coloración de un grafo de incomparabilidad de orden parcial. Este es un grafo con un vértice para cada elemento del orden y una arista para cada par de elementos incomparables. Usando esta interpretación de coloración, junto con una demostración separada del teorema de Dilworth para conjuntos parcialmente ordenados finitos, es posible demostrar que un conjunto parcialmente ordenado infinito tiene anchura finita si y solo si tiene una partición en cadenas., Theorem 5.6, p. 60.

Del mismo modo, el teorema de De Bruijn-Erdős extiende el teorema de los cuatro colores de grafos finitos planares a grafos infinitos planares. Todo grafo finito planar puede colorearse con cuatro colores, según el teorema de los cuatro colores. El teorema de De Bruijn-Erdős demuestra que todo grafo que pueda dibujarse sin intersecciones en el plano, finito o infinito, puede colorearse con cuatro colores. De forma más general, todo grafo infinito cuyos subgrafos finitos sean planares puede colorearse con cuatro colores.. establece el mismo resultado para el teorema de los cinco colores para grafos planares numerables, ya que el teorema de los cuatro colores aún no se había demostrado cuando publicó su estudio, y la demostración del teorema de De Bruijn-Erdős que ofrece solo se aplica a grafos numerables. Para la generalización a grafos en los que todo subgrafo finito es plano (demostrada directamente mediante el teorema de compacidad de Gödel), véase .

Demostraciones La demostración original del teorema de De Bruijn-Erdős, realizada por De Bruijn, utilizó inducción transfinita.

proporcionó la siguiente demostración breve, basada en el teorema de compacidad de Tíjonov en topología. Supóngase que, para el grafo infinito dado , todo subgrafo finito es -coloreable, y sea el espacio de todas las asignaciones de los colores de a los vértices de (independientemente de si forman una coloración válida). Entonces, a se le puede dar una topología como topología producto , donde denota el conjunto de vértices del grafo. Según el teorema de Tíjonov, este espacio topológico es compacto. Para cada subgrafo finito de , sea el subconjunto de que consiste en asignaciones de colores que colorean válidamente . Entonces, el sistema de conjuntos es una familia de conjuntos cerrados con la propiedad de la intersección finita, por lo que, por compacidad, tiene una intersección no vacía. Cada miembro de esta intersección es una coloración válida de .. Gottschalk enuncia su demostración de forma más general como una prueba del teorema de que generaliza el teorema de Bruijn-Erdős.

Una demostración diferente utilizando el lema de Zorn fue proporcionada por Lajos Pósa, y también en la tesis doctoral de 1951 de Gabriel Andrew Dirac. Si es un grafo infinito en el que todo subgrafo finito es -coloreable, entonces, según el lema de Zorn, es un subgrafo de un grafo maximal con la misma propiedad (uno al que no se pueden añadir más aristas sin que algún subgrafo finito requiera más colores que . La relación binaria de no adyacencia en es una relación de equivalencia, y sus clases de equivalencia proporcionan una coloración de . Sin embargo, esta demostración es más difícil de generalizar que la demostración de compacidad.; . Jensen y Toft atribuyen a Gert Sabidussi la observación de que la prueba de Gottschalk es más fácil de generalizar. da la misma prueba a través del lema de Zorn, redescubierto en 2005 por el estudiante universitario Dmytro Karabash.

El teorema también se puede demostrar utilizando ultrafiltros o análisis no estándar. proporciona una prueba para gráficos con un número contable de vértices basada en el lema de Kőnig infinito.

Dependencia de la elección Todas las demostraciones del teorema de De Bruijn-Erdős utilizan alguna forma del axioma de elección. Alguna forma de este supuesto es necesaria, ya que existen modelos de matemáticas en las que tanto el axioma de elección como el teorema de De Bruijn-Erdős son falsos. Más precisamente, demostró que el teorema es una consecuencia del teorema del ideal primo booleano, una propiedad implícita en el axioma de elección, pero más débil que el axioma de elección completo, y demostró que el teorema de De Bruijn-Erdős y el teorema del ideal primo booleano son equivalentes en potencia axiomática.Para conocer esta historia, véase . Para una prueba simplificada del teorema de Läuchli de Mycielski, véase . El teorema de De Bruijn-Erdős para grafos contables también puede demostrarse como equivalente en potencia axiomática, en aritmética de segundo orden, a una forma débil del lema de Konig que establece que todo árbol binario infinito tiene una rama infinita y se utiliza para definir el sistema WKL0.

Como contraejemplo del teorema en modelos de teoría de conjuntos sin elección, sea un grafo infinito cuyos vértices representan todos los números reales posibles. En , se conectan dos números reales, y , mediante una arista siempre que uno de los valores sea . De forma equivalente, en este grafo existen aristas entre todos los números reales racionales y todos los números reales de la forma , para los números racionales . Cada camino en este grafo, a partir de cualquier número real , alterna entre números que difieren de en un número racional más un múltiplo par de y números que difieren de en un número racional más un múltiplo impar de . Esta alternancia impide que contenga ciclos de longitud impar, por lo que cada uno de sus subgrafos finitos solo requiere dos colores. Sin embargo, en el modelo de Solovay, donde todo conjunto de números reales es medible según el método de Lebesgue, el modelo requiere una cantidad infinita de colores, ya que, en este caso, cada clase de color debe ser un conjunto medible y se puede demostrar que todo conjunto medible de números reales sin aristas en debe tener medida cero. Por lo tanto, en el modelo de Solovay, el número cromático (infinito) de todo es mucho mayor que el número cromático de sus subgrafos finitos (como máximo dos).; , pp. 541–542.

Generalizaciones