De Bruijn–Erdős theorem (graph theory)

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.

[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.

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

[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

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.

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.

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.

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.

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

More generally, every infinite graph for which all finite subgraphs are planar can again be four-colored.

[10] Gottschalk (1951) provided the following very short proof, based on Tychonoff's compactness theorem in topology.

[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.

with the same property (one to which no more edges may be added without causing some finite subgraph to require more than

[14] Nash-Williams (1967) gives a proof for graphs with a countable number of vertices based on Kőnig's infinity lemma.

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.

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

be an infinite graph in which the vertices represent all possible real numbers.

Equivalently, in this graph, edges exist between all real numbers

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

Researchers have also investigated other conditions on the subgraphs that are forced to occur in this case.

However, they may have arbitrarily large odd girth, and therefore they may avoid any finite set of non-bipartite subgraphs.

[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.

[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.