De Bruijn–Erdős theorem (graph theory)

This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry).

In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), states that, for every infinite graph G and finite integer k, G can be colored by k colors (with no two adjacent vertices having the same color) if and only if each of its finite subgraphs can be colored by k colors. That is, every k-critical graph (a graph that requires k colors but for which all subgraphs require fewer colors) must have a finite number of vertices.

Proofs

The original proof by De Bruijn used transfinite induction.^[1]

Gottschalk (1951) provided the following very short proof, based on Tychonoff's compactness theorem in topology. Suppose that, for the given infinite graph G, every finite subgraph is k-colorable, and let X be the space of all assignments of the k colors to the vertices of G (regardless of whether they form a valid coloring). Then X may be viewed as a product space k^V(G) which by Tychonoff's theorem is compact. For each finite subgraph F of G, let X_F be the subset of X consisting of assignments of colors that validly color F. Then the system of sets X_F 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 G.^[2]

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 G is an infinite graph in which every finite subgraph is k-colorable, then by Zorn's lemma it is a subgraph of a maximal graph M with the same property (one to which no more edges may be added without causing some finite subgraph to require more than k colors). The binary relation of nonadjacency in M is an equivalence relation and its equivalence classes provide a k-coloring of G. However, this proof is more difficult to generalize than the compactness proof.^[3]

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

Dependence on choice

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.

For example, let G be an infinite graph in which the vertices represent all possible real numbers. In G, connect each two real numbers x and y by an edge whenever the value (|x − y| ± √2) is a rational number. Equivalently, in this graph, edges exist between all real numbers x and all real numbers of the form x ± (√2 + q), where q is any rational number). Thus, if two vertices in G differ by an even integer multiple of the square root of two plus a rational number, the two require the same color and may be considered equivalent; the graph formed by contracting each equivalence class to a single vertex is an infinite matching and may easily be two-colored using the axiom of choice. Therefore, every finite subgraph of G requires two colors. However, in the Solovay model in which every set of real numbers is Lebesgue measurable, G 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 G must have measure zero. Therefore, in the Solovay model, the (infinite) chromatic number of all of G is much larger than the chromatic number of its finite subgraphs (at most two).^[6]

The De Bruijn–Erdős theorem for countable graphs can be shown to be equivalent in axiomatic power, within a theory of second-order arithmetic, to König's infinity lemma.^[7]

Applications

A seven-coloring of the plane, and a four-chromatic unit distance graph in the plane, providing upper and lower bounds for the Hadwiger–Nelson problem.

One application of the De Bruijn–Erdős theorem is to the Hadwiger–Nelson problem concerning the chromatic number of the unit distance graph of the Euclidean plane. The graph of the plane has an uncountable number of vertices, one for every point in the plane. Two vertices are connected by an edge whenever the Euclidean distance between the corresponding two points is exactly one. This infinite graph has finite subgraphs such as the Moser spindle that require four colors, and it has a known coloring with seven colors based on a hexagonal tiling of the plane. Therefore, the chromatic number of the plane must belong to the set {4,5,6,7}, but it is not known which of these four 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 four then this fact can be proved by a finite calculation.^[8]

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 (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 w if and only if it has a partition into w chains.^[9]

In the same way, the De Bruijn–Erdős theorem extends the four-color theorem from finite planar graphs to infinite planar graphs: 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.^[10]

The De Bruijn–Erdős theorem may also be used to answer a question of Fred Galvin concerning an intermediate value theorem for graph chromatic numbers: for every two finite numbers j < k, and every graph G with chromatic number k, there is a subgraph of G with chromatic number j. To see this, find a finite subgraph of G with the same chromatic number as G itself, and then delete vertices one by one until the target chromatic number j is reached. However, the situation for infinite chromatic numbers is more complicated: it is consistent with set theory that there exists a graph with ℵ₂ vertices, and with chromatic number ℵ₂, but with no subgraph of chromatic number ℵ₁.^[11]

Generalizations

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

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 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.^[13]

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 k-coloring if and only if each of its finite sub-hypergraphs has a k-coloring.^[14] 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.

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 G and cardinal number μ < κ, G has chromatic number at most μ if and only if each of its subgraphs of cardinality less than κ has chromatic number at most μ.^[15] 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 G of cardinality (2^γ)⁺ such that the chromatic number of G is greater than γ, but such that every subgraph of G whose vertex set has smaller power than G has chromatic number at most γ.^[16] 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.

Notes

1. ^ Soifer (2008) (p. 236).
2. ^ 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.
3. ^ Jensen & Toft (1995); Harzheim (2005). Jensen and Toft attribute to Gert Sabidussi the observation that Gottschalk's proof is easier to generalize. Soifer (pp. 238–239) gives the same proof via Zorn's lemma, rediscovered in 2005 by undergraduate student Dmytro Karabash.
4. ^ Luxemburg (1962).
5. ^ Hurd & Loeb (1985).
6. ^ Shelah & Soifer (2003); Soifer (2008), pp. 541–542.
7. ^ Schmerl (2000).
8. ^ Soifer (2008), p. 39.
9. ^ Harzheim (2005), Theorem 5.6, p. 60.
10. ^ 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, Wolfgang (2009), A Concise Introduction to Mathematical Logic, Universitext (3rd ed.), Springer-Verlag, p. 32, ISBN 9781441912206, http://books.google.com/books?id=vMwixYpQTocC&pg=PA32 .
11. ^ Komjáth (1988); Komjáth (2011).
12. ^ 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).
13. ^ Erdős & Hajnal (1966); Komjáth (2011).
14. ^ Soifer (2008), p. 239.
15. ^ 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, Akihiro (2008), The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag, p. 37, ISBN 9783540888666, http://books.google.com/books?id=FH_n84ocuSMC&pg=PA37 .
16. ^ Erdős & Hajnal (1968).

References

• Barnette, David (1983), Map Coloring, Polyhedra, and the Four-Color Problem, Dolciani Mathematical Expositions, 8, Mathematical Association of America, p. 160, ISBN 9780883853092 .
• de Bruijn, N. G.; Erdős, P. (1951), "A colour problem for infinite graphs and a problem in the theory of relations", Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373, MR0046630, http://www.math-inst.hu/~p_erdos/1951-01.pdf .
• Erdős, P.; Hajnal, A. (1966), "On chromatic number of graphs and set-systems", Acta Mathematica Academiae Scientiarum Hungaricae 17: 61–99, doi:10.1007/BF02020444, MR0193025, http://www.renyi.hu/~p_erdos/1966-07.pdf .
• Erdős, P.; Hajnal, A. (1968), "On chromatic number of infinite graphs", Theory of Graphs (Proc. Colloq., Tihany, 1966), New York: Academic Press, pp. 83–98, MR0263693, http://www.renyi.hu/~p_erdos/1968-04.pdf .
• Gottschalk, W. H. (1951), "Choice functions and Tychonoff's theorem", Proceedings of the American Mathematical Society 2: 172, MR0040376 .
• Harzheim, Egbert (2005), Ordered sets, Advances in Mathematics, 7, New York: Springer, Theorem 5.5, p. 59, ISBN 0-387-24219-8, MR2127991, http://books.google.com/books?id=FYV6tGm3NzgC&pg=PA59 .
• Hurd, Albert E.; Loeb, Peter A. (1985), An introduction to nonstandard real analysis, Pure and Applied Mathematics, 118, Orlando, FL: Academic Press, Theorem 5.14, p. 92, ISBN 0-12-362440-1, MR806135, http://books.google.com/books?id=jgH3mmbs59IC&pg=PA92 .
• 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, MR1304254 .
• Komjáth, Péter (1988), "Consistency results on infinite graphs", Israel Journal of Mathematics 61 (3): 285–294, doi:10.1007/BF02772573, MR941243 .
• Komjáth, Péter (2011), "The chromatic number of infinite graphs—A survey", Discrete Mathematics 311 (15): 1448–1450, doi:10.1016/j.disc.2010.11.004, http://matmod.elte.hu/~kope/offp50.pdf .
• 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: 170–174, MR0360335 .
• Luxemburg, W. A. J. (1962), "A remark on a paper by N. G. de Bruijn and P. Erdős", Indagationes Mathematicae 24: 343–345, MR0140435 .
• Nash-Williams, C. St. J. A. (1967), "Infinite graphs—a survey", Journal of Combinatorial Theory 3: 286–301, MR0214501 .
• Rado, R. (1949), "Axiomatic treatment of rank in infinite sets", Canadian Journal of Mathematics 1: 337–343, http://www.cms.math.ca/cjm/v1/p337 .
• 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, MR1791549 .
• 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, MR1996076 .
• Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, ISBN 978-0387746401 . 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.