In
graph theory, the **De Bruijn–Erdős theorem** relates
graph coloring of an
infinite graph to the same problem on its finite
subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by
Nicolaas Govert de Bruijn and
Paul Erdős (
1951), after whom it is named.

The De Bruijn–Erdős theorem has several different proofs, all depending in some way on the axiom of choice. Its applications include extending the four-color theorem and Dilworth's theorem from finite graphs and partially ordered sets to infinite ones, and reducing the Hadwiger–Nelson problem on the chromatic number of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose cardinality is a strongly compact cardinal.

An
undirected graph is a mathematical object consisting of a set of
vertices and a set of
edges that link pairs of vertices. The two vertices associated with each edge are called its endpoints. The graph is finite when its vertices and edges form
finite sets, and infinite otherwise. A
graph coloring associates each vertex with a color drawn from a set of colors, in such a way that every edge has two different colors at its endpoints. A frequent goal in graph coloring is to minimize the total number of colors that are used; the
chromatic number of a graph is this minimum number of colors.^{
[1]} The
four-color theorem states that every finite graph that can be drawn without crossings in the
Euclidean plane needs at most four colors; however, some graphs with more complicated connectivity require more than four colors.^{
[2]} It is a consequence of the
axiom of choice that the chromatic number is
well-defined for infinite graphs, but for these graphs the chromatic number might itself be an infinite
cardinal number.^{
[3]}

A
subgraph of a graph is another graph obtained from a subset of its vertices and a subset of its edges. If the larger graph is colored, the same coloring can be used for the subgraph. Therefore, the chromatic number of a subgraph cannot be larger than the chromatic number of the whole graph. The De Bruijn–Erdős theorem concerns the chromatic numbers of infinite graphs, and shows that (again, assuming the axiom of choice) they can be calculated from the chromatic numbers of their finite subgraphs. It states that, if the chromatic numbers of the finite subgraphs of a graph have a finite maximum value , then the chromatic number of itself is exactly . On the other hand, if there is no finite
upper bound on the chromatic numbers of the finite subgraphs of , then the chromatic number of itself must be infinite.^{
[4]}

The original motivation of Erdős in studying this problem was to extend from finite to infinite graphs the theorem that, whenever a graph has an
orientation with finite maximum out-degree , it also has a -coloring. For finite graphs this follows because such graphs always have a vertex of degree at most , which can be colored with one of colors after all the remaining vertices are colored recursively. Infinite graphs with such an orientation do not always have a low-degree vertex (for instance,
Bethe lattices have but arbitrarily large minimum degree), so this argument requires the graph to be finite. But the De Bruijn–Erdős theorem shows that a -coloring exists even for infinite graphs.^{
[5]}

Another application of the De Bruijn–Erdős theorem is to the
Hadwiger–Nelson problem, which asks how many colors are needed to color the points of the
Euclidean plane so that every two points that are a unit distance apart have different colors. This is a
graph coloring problem for an infinite graph that has a vertex for every point of the plane and an edge for every two points whose
Euclidean distance is exactly one. The
induced subgraphs of this graph are called
unit distance graphs. A seven-vertex unit distance graph, the
Moser spindle, requires four colors; in 2018, much larger unit distance graphs were found that require five colors.^{
[6]} The whole infinite graph has a known coloring with seven colors based on a hexagonal tiling of the plane. Therefore, the chromatic number of the plane must be either 5, 6, or 7, but it is not known which of these three numbers is the correct value. The De Bruijn–Erdős theorem shows that, for this problem, there exists a finite unit distance graph with the same chromatic number as the whole plane, so if the chromatic number is greater than five then this fact can be proved by a finite calculation.^{
[7]}

The De Bruijn–Erdős theorem may also be used to extend
Dilworth's theorem from finite to infinite
partially ordered sets. Dilworth's theorem states that the width of a partial order (the maximum number of elements in a set of mutually incomparable elements) equals the minimum number of chains (
totally ordered subsets) into which the partial order may be partitioned. A partition into chains may be interpreted as a coloring of the
incomparability graph of the partial order. This is a graph with a vertex for each element of the order and an edge for each pair of incomparable elements. Using this coloring interpretation, together with a separate proof of Dilworth's theorem for finite partially ordered sets, it is possible to prove that an infinite partially ordered set has finite width if and only if it has a partition into chains.^{
[8]}

In the same way, the De Bruijn–Erdős theorem extends the
four-color theorem from finite planar graphs to infinite planar graphs. Every finite planar graph can be colored with four colors, by the four-color theorem. The De Bruijn–Erdős theorem then shows that
every graph that can be drawn without crossings in the plane, finite or infinite, can be colored with four colors. More generally, every infinite graph for which all finite subgraphs are planar can again be four-colored.^{
[9]}

The original proof of the De Bruijn–Erdős theorem, by De Bruijn, used
transfinite induction.^{
[10]}

Gottschalk (1951) provided the following very short proof, based on
Tychonoff's
compactness theorem in topology. Suppose that, for the given infinite graph , every finite subgraph is -colorable, and let be the space of all assignments of the colors to the vertices of (regardless of whether they form a valid coloring). Then may be given a topology as a
product space , where denotes the set of vertices of the graph. By Tychonoff's theorem this topological space is
compact. For each finite subgraph of , let be the subset of consisting of assignments of colors that validly color . Then the system of sets is a family of
closed sets with the
finite intersection property, so by compactness it has a nonempty intersection. Every member of this intersection is a valid coloring of .^{
[11]}

A different proof using
Zorn's lemma was given by
Lajos Pósa, and also in the 1951 Ph.D. thesis of
Gabriel Andrew Dirac. If is an infinite graph in which every finite subgraph is -colorable, then by Zorn's lemma it is a subgraph of a
maximal graph with the same property (one to which no more edges may be added without causing some finite subgraph to require more than colors). The
binary relation of nonadjacency in is an
equivalence relation, and its equivalence classes provide a -coloring of . However, this proof is more difficult to generalize than the compactness proof.^{
[12]}

The theorem can also be proved using
ultrafilters^{
[13]} or
non-standard analysis.^{
[14]}
Nash-Williams (1967) gives a proof for graphs with a countable number of vertices based on
Kőnig's infinity lemma.

All proofs of the De Bruijn–Erdős theorem use some form of the
axiom of choice. Some form of this assumption is necessary, as there exist
models of mathematics in which both the axiom of choice and the De Bruijn–Erdős theorem are false. More precisely,
Mycielski (1961) showed that the theorem is a consequence of the
Boolean prime ideal theorem, a property that is implied by the axiom of choice but weaker than the full axiom of choice, and
Läuchli (1971) showed that the De Bruijn–Erdős theorem and the Boolean prime ideal theorem are equivalent in axiomatic power.^{
[15]}
The De Bruijn–Erdős theorem for countable graphs can also be shown to be equivalent in axiomatic power, within a theory of
second-order arithmetic, to Kőnig's infinity lemma.^{
[16]}

For a counterexample to the theorem in models of set theory without choice, let be an infinite graph in which the vertices represent all possible real numbers. In , connect each two real numbers and by an edge whenever one of the values is a
rational number. Equivalently, in this graph, edges exist between all real numbers and all real numbers of the form , for rational numbers . Each path in this graph, starting from any real number ,
alternates between numbers that differ from by a rational number plus an even multiple of
and numbers that differ from by a rational number plus an odd multiple of .
This alternation prevents from containing any cycles of odd length, so each of its finite subgraphs
requires only two colors. However, in the
Solovay model in which every set of real numbers is
Lebesgue measurable, requires infinitely many colors, since in this case each color class must be a measurable set and it can be shown that every measurable set of real numbers with no edges in must have measure zero. Therefore, in the Solovay model, the (infinite) chromatic number of all of is much larger than the chromatic number of its finite subgraphs (at most two).^{
[17]}

Rado (1949) proves the following theorem, which may be seen as a generalization of the De Bruijn–Erdős theorem. Let be an infinite set, for instance the set of vertices in an infinite graph. For each element of , let be a finite set of colors. Additionally, for every finite subset of , choose some particular coloring of , in which the color of each element of belongs to . Then there exists a global coloring of all of with the property that every finite set has a finite superset on which and agree. In particular, if we choose a -coloring for every finite subgraph of an infinite graph , then there is a -coloring of in which each finite graph has a larger supergraph whose coloring agrees with the coloring of the whole graph.^{
[18]}

If a graph does not have finite chromatic number, then the De Bruijn–Erdős theorem implies that it must contain finite subgraphs of every possible finite chromatic number. Researchers have also investigated other conditions on the subgraphs that are forced to occur in this case. For instance, unboundedly chromatic graphs must also contain every possible finite
bipartite graph as a subgraph. However, they may have arbitrarily large
odd girth, and therefore they may avoid any finite set of non-bipartite subgraphs.^{
[19]}

The De Bruijn–Erdős theorem also applies directly to
hypergraph coloring problems, where one requires that each hyperedge have vertices of more than one color. As for graphs, a hypergraph has a -coloring if and only if each of its finite sub-hypergraphs has a -coloring.^{
[20]} It is a special case of the
compactness theorem of
Kurt Gödel, stating that a set of
first-order sentences has a
model if and only if every finite
subset of it has a model.^{
[21]} More specifically, the De Bruijn–Erdős theorem can be interpreted as the compactness of the first-order
structures whose non-logical values are any finite set of colors and whose only predicate on these values is inequality.^{
[22]}

The theorem may also be generalized to situations in which the number of colors is an infinite
cardinal number. If is a
strongly compact cardinal, then for every graph and cardinal number , has chromatic number at most if and only if each of its subgraphs of cardinality less than has chromatic number at most .^{
[23]} The original De Bruijn–Erdős theorem is the case of this generalization, since a set is finite if and only if its cardinality is less than . However, some assumption such as the one of being a strongly compact cardinal is necessary: if the
generalized continuum hypothesis is true, then for every infinite cardinal , there exists a graph of cardinality such that the chromatic number of is greater than , but such that every subgraph of whose vertex set has smaller power than has chromatic number at most .^{
[24]}
Lake (1975) characterizes the infinite graphs that obey a generalization of the De Bruijn–Erdős theorem, in that their chromatic number is equal to the maximum chromatic number of their strictly smaller subgraphs.

**^**For these basic definitions, see Jensen & Toft (1995), pp. 1–2.**^**Jensen & Toft (1995), p. 5.**^**Komjáth (2011).**^**Jensen & Toft (1995), Theorem 1, p. 2.**^**Erdős (1950). See in particular p. 137, where the De Bruijn–Erdős theorem is first announced (but not proven), with a hint that Kőnig's lemma can be used for countable graphs.**^**Lamb (2018).**^**Soifer (2008), p. 39.**^**Harzheim (2005), Theorem 5.6, p. 60.**^**Barnette (1983). Nash-Williams (1967) states the same result for the five-color theorem for countable planar graphs, as the four-color theorem had not yet been proven when he published his survey, and as the proof of the De Bruijn–Erdős theorem that he gives only applies to countable graphs. For the generalization to graphs in which every finite subgraph is planar (proved directly via Gödel's compactness theorem), see Rautenberg (2010).**^**Soifer (2008), p. 236.**^**Jensen & Toft (1995). Gottschalk states his proof more generally as a proof of the theorem of Rado (1949) that generalizes the De Bruijn–Erdős theorem.**^**Jensen & Toft (1995); Harzheim (2005). Jensen and Toft attribute to Gert Sabidussi the observation that Gottschalk's proof is easier to generalize. Soifer (2008, pp. 238–239) gives the same proof via Zorn's lemma, rediscovered in 2005 by undergraduate student Dmytro Karabash.**^**Luxemburg (1962).**^**Hurd & Loeb (1985).**^**For this history, see Cowen, Hechler & Mihók (2002). For a simplified proof of Läuchli's theorem by Mycielski, see Cowen (1990).**^**Schmerl (2000).**^**Shelah & Soifer (2003); Soifer (2008), pp. 541–542.**^**For this connection between Rado's lemma and the De Bruijn–Erdős theorem, see e.g. the discussion following Theorem A of Nash-Williams (1967).**^**Erdős & Hajnal (1966); Komjáth (2011).**^**Soifer (2008), p. 239.**^**Lake (1975), p. 171: "It is straightforward to prove [the De Bruijn–Erdős theorem] using the compactness theorem for first-order logic"**^**Rorabaugh, Tardif & Wehlau (2017).**^**This follows immediately from the definition of a strongly compact cardinal as being a cardinal such that every collection of formulae of infinitary logic each of length smaller than , that is satisfiable for every subcollection of fewer than formulae, is globally satisfiable. See e.g. Kanamori (2008).**^**Erdős & Hajnal (1968).

- Barnette, David (1983),
*Map Coloring, Polyhedra, and the Four-Color Problem*, Dolciani Mathematical Expositions, vol. 8, Mathematical Association of America, p. 160, ISBN 978-0-88385-309-2. -
De Bruijn, N. G.;
Erdős, P. (1951),
"A colour problem for infinite graphs and a problem in the theory of relations" (PDF),
*Nederl. Akad. Wetensch. Proc. Ser. A*,**54**: 371–373, doi: 10.1016/S1385-7258(51)50053-7, MR 0046630, archived from the original (PDF) on 2016-03-10, retrieved 2010-04-05. - Cowen, Robert H. (1990), "Two hypergraph theorems equivalent to BPI",
*Notre Dame Journal of Formal Logic*,**31**(2): 232–240, doi: 10.1305/ndjfl/1093635418, MR 1058424. - Cowen, Robert; Hechler, Stephen H.; Mihók, Peter (2002), "Graph coloring compactness theorems equivalent to BPI",
*Scientiae Mathematicae Japonicae*,**56**(2): 213–223, CiteSeerX 10.1.1.23.1521, MR 1922784. -
Erdős, P. (1950),
"Some remarks on set theory" (PDF),
*Proceedings of the American Mathematical Society*,**1**(2): 127–141, doi: 10.2307/2031913, JSTOR 2031913, MR 0035809. -
Erdős, P.;
Hajnal, A. (1966),
"On chromatic number of graphs and set-systems" (PDF),
*Acta Mathematica Academiae Scientiarum Hungaricae*,**17**(1–2): 61–99, doi: 10.1007/BF02020444, MR 0193025, S2CID 189780485. -
Erdős, P.;
Hajnal, A. (1968), "On chromatic number of infinite graphs",
*Theory of Graphs (Proc. Colloq., Tihany, 1966)*(PDF), New York: Academic Press, pp. 83–98, MR 0263693. -
Gottschalk, W. H. (1951), "Choice functions and Tychonoff's theorem",
*Proceedings of the American Mathematical Society*,**2**(1): 172, doi: 10.2307/2032641, JSTOR 2032641, MR 0040376. - Harzheim, Egbert (2005),
*Ordered sets*, Advances in Mathematics, vol. 7, New York: Springer, Theorem 5.5, p. 59, ISBN 0-387-24219-8, MR 2127991. - Hurd, Albert E.;
Loeb, Peter A. (1985),
*An introduction to nonstandard real analysis*, Pure and Applied Mathematics, vol. 118, Orlando, FL: Academic Press, Theorem 5.14, p. 92, ISBN 0-12-362440-1, MR 0806135. - Jensen, Tommy R.; Toft, Bjarne (1995),
*Graph coloring problems*, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons Inc., Theorem 1, pp. 2–3, ISBN 0-471-02865-7, MR 1304254. -
Kanamori, Akihiro (2008),
*The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings*, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag, p. 37, ISBN 978-3-540-88866-6. -
Komjáth, Péter (2011),
"The chromatic number of infinite graphs—A survey" (PDF),
*Discrete Mathematics*,**311**(15): 1448–1450, doi: 10.1016/j.disc.2010.11.004. - Lake, John (1975), "A generalization of a theorem of de Bruijn and Erdős on the chromatic number of infinite graphs",
*Journal of Combinatorial Theory*, Series B,**18**(2): 170–174, doi: 10.1016/0095-8956(75)90044-1, MR 0360335. - Lamb, Evelyn (April 17, 2018),
"Decades-old graph problem yields to amateur mathematician",
*Quanta Magazine* - Läuchli, H. (1971), "Coloring infinite graphs and the Boolean prime ideal theorem",
*Israel Journal of Mathematics*,**9**(4): 422–429, doi: 10.1007/BF02771458, MR 0288051. -
Luxemburg, W. A. J. (1962), "A remark on a paper by N. G. de Bruijn and P. Erdős",
*Indagationes Mathematicae*,**24**: 343–345, doi: 10.1016/S1385-7258(62)50033-4, MR 0140435. -
Mycielski, Jan (1961), "Some remarks and problems on the colouring of infinite graphs and the theorem of Kuratowski",
*Acta Mathematica Academiae Scientiarum Hungaricae*,**12**(1–2): 125–129, doi: 10.1007/BF02066677, MR 0130686, S2CID 120141460. -
Nash-Williams, C. St. J. A. (1967), "Infinite graphs—a survey",
*Journal of Combinatorial Theory*,**3**(3): 286–301, doi: 10.1016/s0021-9800(67)80077-2, MR 0214501. -
Rado, R. (1949), "Axiomatic treatment of rank in infinite sets",
*Canadian Journal of Mathematics*,**1**(4): 337–343, doi: 10.4153/cjm-1949-031-1, S2CID 124598982. -
Rautenberg, Wolfgang (2010),
*A Concise Introduction to Mathematical Logic*, Universitext (3rd ed.), Springer-Verlag, p. 32, doi: 10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6. - Rorabaugh, Danny; Tardif, Claude; Wehlau, David (2017), "Logical compactness and constraint satisfaction problems",
*Logical Methods in Computer Science*,**13**(1): 1:1–1:11, arXiv: 1609.05221, doi: 10.23638/LMCS-13(1:1)2017, MR 3607036, S2CID 31135533. - Schmerl, James H. (2000), "Graph coloring and reverse mathematics",
*Mathematical Logic Quarterly*,**46**(4): 543–548, doi: 10.1002/1521-3870(200010)46:4<543::AID-MALQ543>3.0.CO;2-E, MR 1791549. -
Shelah, Saharon;
Soifer, Alexander (2003), "Axiom of choice and chromatic number of the plane",
*Journal of Combinatorial Theory*, Series A,**103**(2): 387–391, doi: 10.1016/S0097-3165(03)00102-X, MR 1996076. -
Soifer, Alexander (2008),
*The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators*, New York: Springer, ISBN 978-0-387-74640-1. See especially Chapter II.5 "De Bruin–Erdős reduction to finite sets and results near the lower bound", pp. 39–42, and Chapter V.26 "De Bruin–Erdős's theorem and its history", pp. 236–241.