De Bruijn–Erdős theorem
Encyclopedia
In graph theory
, the De Bruijn–Erdős theorem, proved by , states that, for every infinite graph and finite integer , can be colored
by colors (with no two adjacent vertices having the same color) if and only if each of its finite subgraphs can be colored by colors. That is, every -critical graph
(a graph that requires colors but for which all subgraphs require fewer colors) must have a finite number of vertices.
.
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 viewed as a product space which by Tychonoff's theorem 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 set
s with the finite intersection property
, so by compactness it has a nonempty intersection. Every member of this intersection is a valid coloring of .
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.
The theorem can also be proved using ultrafilter
s or non-standard analysis
. gives a proof for graphs with a countable number of vertices based on König's infinity lemma
.
of mathematics in which both the axiom of choice and the De Bruijn–Erdős theorem are false.
For example, 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 the value is a rational number
. Equivalently, in this graph, edges exist between all real numbers and all real numbers of the form , where q is any rational number). Thus, if two vertices in 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 requires 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).
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.
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.
The De Bruijn–Erdős theorem may also be used to extend Dilworth's theorem
from finite to infinite partially ordered set
s. 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 if and only if it has a partition into chains.
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.
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 , and every graph with chromatic number , there is a subgraph of with chromatic number . To see this, find a finite subgraph of with the same chromatic number as itself, and then delete vertices one by one until the target chromatic number 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 .
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.
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. 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 μ. The original De Bruijn–Erdős theorem is the case κ = ℵ0 of this generalization, since a set is finite if and only if its cardinality is less than ℵ0. 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 (2γ)+ 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 . 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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the De Bruijn–Erdős theorem, proved by , states that, for every infinite graph and finite integer , can be colored
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
by colors (with no two adjacent vertices having the same color) if and only if each of its finite subgraphs can be colored by colors. That is, every -critical graph
Critical graph
In general the notion of criticality can refer to any measure.But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a graph....
(a graph that requires 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 inductionTransfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
.
provided the following very short proof, based on Tychonoff
Andrey Nikolayevich Tychonoff
Andrey Nikolayevich Tikhonov was a Soviet and Russian mathematician known for important contributions to topology, functional analysis, mathematical physics, and ill-posed problems. He was also inventor of magnetotellurics method in geology. Tikhonov originally published in German, whence the...
's compactness theorem
Tychonoff's theorem
In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact. The theorem is named after Andrey Nikolayevich Tychonoff, who proved it first in 1930 for powers of the closed unit interval and in 1935 stated the full theorem along with the...
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 viewed as a product space which by Tychonoff's theorem is compact
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
. 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 set
Closed set
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points...
s with the finite intersection property
Finite intersection property
In general topology, a branch of mathematics, the finite intersection property is a property of a collection of subsets of a set X. A collection has this property if the intersection over any finite subcollection of the collection is nonempty....
, so by compactness it has a nonempty intersection. Every member of this intersection is a valid coloring of .
A different proof using Zorn's lemma
Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Suppose a partially ordered set P has the property that every chain has an upper bound in P...
was given by Lajos Pósa
Lajos Pósa
Lajos Pósa was a Hungarian writer and poet. He created and edited a children's literary journal....
, and also in the 1951 Ph.D. thesis of Gabriel Andrew Dirac
Gabriel Andrew Dirac
Gabriel Andrew Dirac was a mathematician who mainly worked in graph theory. He stated a sufficient condition for a graph to contain a Hamiltonian circuit.Dirac received his Ph.D...
. If is an infinite graph in which every finite subgraph is -colorable, then by Zorn's lemma it is a subgraph of a maximal
Maximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
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
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
of nonadjacency in is an equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
and its equivalence classes provide a -coloring of . However, this proof is more difficult to generalize than the compactness proof.
The theorem can also be proved using ultrafilter
Ultrafilter
In the mathematical field of set theory, an ultrafilter on a set X is a collection of subsets of X that is a filter, that cannot be enlarged . An ultrafilter may be considered as a finitely additive measure. Then every subset of X is either considered "almost everything" or "almost nothing"...
s or non-standard analysis
Non-standard analysis
Non-standard analysis is a branch of mathematics that formulates analysis using a rigorous notion of an infinitesimal number.Non-standard analysis was introduced in the early 1960s by the mathematician Abraham Robinson. He wrote:...
. gives a proof for graphs with a countable number of vertices based on König's infinity lemma
König's lemma
König's lemma or König's infinity lemma is a theorem in graph theory due to Dénes Kőnig . It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic,...
.
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 modelsModel theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
of mathematics in which both the axiom of choice and the De Bruijn–Erdős theorem are false.
For example, 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 the value is a rational number
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
. Equivalently, in this graph, edges exist between all real numbers and all real numbers of the form , where q is any rational number). Thus, if two vertices in 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 requires two colors. However, in the Solovay model
Solovay model
In the mathematical field of set theory, the Solovay model is a model constructed by in which all of the axioms of Zermelo–Fraenkel set theory hold, exclusive of the axiom of choice, but in which all sets of real numbers are Lebesgue measurable...
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).
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
Second-order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. It was introduced by David Hilbert and Paul Bernays in their...
, to König's infinity lemma.
Applications
Hadwiger–Nelson problem
In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance one from each other have the same color. The answer is unknown, but has been narrowed down to...
concerning the chromatic number of the unit distance graph
Unit distance graph
In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one...
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
Euclidean distance
In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
between the corresponding two points is exactly one. This infinite graph has finite subgraphs such as the Moser spindle
Moser spindle
In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges...
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.
The De Bruijn–Erdős theorem may also be used to extend Dilworth's theorem
Dilworth's theorem
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains...
from finite to infinite partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
s. 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
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
subsets) into which the partial order may be partitioned. A partition into chains may be interpreted as a coloring of the incomparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
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 if and only if it has a partition into chains.
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.
The De Bruijn–Erdős theorem may also be used to answer a question of Fred Galvin
Fred Galvin
Frederick William Galvin is a mathematician, currently a professor at the University of Kansas. His research interests include set theory and combinatorics.His notable combinatorial work includes the proof of the Dinitz conjecture...
concerning an intermediate value theorem
Intermediate value theorem
In mathematical analysis, the intermediate value theorem states that for each value between the least upper bound and greatest lower bound of the image of a continuous function there is at least one point in its domain that the function maps to that value....
for graph chromatic numbers: for every two finite numbers , and every graph with chromatic number , there is a subgraph of with chromatic number . To see this, find a finite subgraph of with the same chromatic number as itself, and then delete vertices one by one until the target chromatic number 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 .
Generalizations
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.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
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
as a subgraph. However, they may have arbitrarily large odd girth, and therefore they may avoid any finite set of non-bipartite subgraphs.
The De Bruijn–Erdős theorem also applies directly to hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
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. It is a special case of the compactness theorem
Compactness theorem
In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model...
of Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
stating that a set of first-order sentences has a model
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
if and only if every finite subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of it has a model.
The theorem may also be generalized to situations in which the number of colors is an infinite cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
: if κ is a strongly compact cardinal
Strongly compact cardinal
In mathematical set theory, a strongly compact cardinal is a certain kind of large cardinal number; their existence can neither be proven nor disproven from the standard axioms of set theory....
, 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 μ. The original De Bruijn–Erdős theorem is the case κ = ℵ0 of this generalization, since a set is finite if and only if its cardinality is less than ℵ0. 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 (2γ)+ 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 . 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.