De Bruijn–Erdős theorem (graph theory)
   HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the De Bruijn–Erdős theorem relates
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 o ...
of an
infinite graph This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...
to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with c colors, the same is true for the whole graph. The theorem was proved by
Nicolaas Govert de Bruijn Nicolaas Govert (Dick) de Bruijn (; 9 July 1918 – 17 February 2012) was a Dutch mathematician, noted for his many contributions in the fields of analysis, number theory, combinatorics and logic.
and
Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
(
1951 Events January * January 4 – Korean War: Third Battle of Seoul – Chinese and North Korean forces capture Seoul for the second time (having lost the Second Battle of Seoul in September 1950). * January 9 – The Government of the United ...
), 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 In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
. Its applications include extending the
four-color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...
and
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. It is named for the mathematician . ...
from finite graphs and
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
s to infinite ones, and reducing the
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 1 from each other have the same color. ...
on the
chromatic number 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 o ...
of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
is a
strongly compact cardinal In set theory, a branch of mathematics, a strongly compact cardinal is a certain kind of large cardinal. A cardinal κ is strongly compact if and only if every κ-complete filter can be extended to a κ-complete ultrafilter. Strongly compact cardi ...
.


Definitions and statement

An
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
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 set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...
s, and infinite otherwise. A
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 o ...
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 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 o ...
of a graph is this minimum number of colors. The
four-color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...
states that every finite graph that can be drawn without crossings in the
Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
needs at most four colors; however, some graphs with more complicated connectivity require more than four colors. It is a consequence of the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
that the chromatic number is
well-defined In mathematics, a well-defined expression or unambiguous expression is an expression whose definition assigns it a unique interpretation or value. Otherwise, the expression is said to be ''not well defined'', ill defined or ''ambiguous''. A funct ...
for infinite graphs, but for these graphs the chromatic number might itself be an infinite
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
. 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 G have a finite maximum value c, then the chromatic number of G itself is exactly c. On the other hand, if there is no finite
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an element ...
on the chromatic numbers of the finite subgraphs of G, then the chromatic number of G itself must be infinite.


Applications

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 Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building de ...
with finite maximum out-degree k, it also has a (2k+1)-coloring. For finite graphs this follows because such graphs always have a vertex of degree at most 2k, which can be colored with one of 2k+1 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 lattice In statistical mechanics and mathematics, the Bethe lattice (also called a regular tree) is an infinite connected cycle-free graph where all vertices have the same number of neighbors. The Bethe lattice was introduced into the physics literature ...
s have k=1 but arbitrarily large minimum degree), so this argument requires the graph to be finite. But the De Bruijn–Erdős theorem shows that a (2k+1)-coloring exists even for infinite graphs. Another application of the De Bruijn–Erdős theorem is to the
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 1 from each other have the same color. ...
, which asks how many colors are needed to color the points of the
Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
so that every two points that are a unit distance apart have different colors. This is a
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 o ...
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 In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
is exactly one. The
induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...
s of this graph are called
unit distance graph In mathematics, 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 whenever the distance between them is exactly one. To distinguish these graph ...
s. A seven-vertex unit distance graph, the
Moser spindle In graph theory, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit d ...
, requires four colors; in 2018, much larger unit distance graphs were found that require five colors. 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. The De Bruijn–Erdős theorem may also be used to extend
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. It is named for the mathematician . ...
from finite to infinite
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
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 In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
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 w if and only if it has a partition into w chains. In the same way, the De Bruijn–Erdős theorem extends the
four-color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...
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.


Proofs

The original proof of the De Bruijn–Erdős theorem, by De Bruijn, used
transfinite induction Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for a ...
. provided the following very short proof, based on Tychonoff's
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. This theorem is an important tool in model theory, as it provides a useful (but generally no ...
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 given a topology as a
product space In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seemin ...
k^, where V(G) denotes the set of vertices of the graph. By Tychonoff's theorem this topological space is
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in British ...
. 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 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. In a complete metric space, a cl ...
s with the
finite intersection property In general topology, a branch of mathematics, a non-empty family ''A'' of subsets of a set X is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of A is non-empty. It has the strong finite inters ...
, so by compactness it has a nonempty intersection. Every member of this intersection is a valid coloring of G. 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 Gabriel Andrew Dirac (13 March 1925 – 20 July 1984) was a Hungarian/British mathematician who mainly worked in graph theory. He served as Erasmus Smith's Professor of Mathematics at Trinity College Dublin 1964-1966. In 1952, he gave a sufficie ...
. 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 In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
of nonadjacency in M is an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relation ...
, and its equivalence classes provide a k-coloring of G. However, this proof is more difficult to generalize than the compactness proof. The theorem can also be proved using
ultrafilter In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a maximal filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filter on ...
s or
non-standard analysis The history of calculus is fraught with philosophical debates about the meaning and logical validity of fluxions or infinitesimal numbers. The standard way to resolve these debates is to define the operations of calculus using epsilon–delta ...
. 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 In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
. Some form of this assumption is necessary, as there exist
models A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
of mathematics in which both the axiom of choice and the De Bruijn–Erdős theorem are false. More precisely, showed that the theorem is a consequence of the
Boolean prime ideal theorem In mathematics, the Boolean prime ideal theorem states that Ideal (order theory), ideals in a Boolean algebra (structure), Boolean algebra can be extended to Ideal (order theory)#Prime ideals , prime ideals. A variation of this statement for Filt ...
, a property that is implied by the axiom of choice but weaker than the full axiom of choice, and showed that the De Bruijn–Erdős theorem and the Boolean prime ideal theorem are equivalent in axiomatic power. 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 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. A precurs ...
, to Kőnig's infinity lemma. For a counterexample to the theorem in models of set theory without choice, 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 one of the values , x-y, \pm\sqrt2 is a
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
. Equivalently, in this graph, edges exist between all real numbers x and all real numbers of the form x+q\pm\sqrt2, for rational numbers q. Each path in this graph, starting from any real number x, alternates between numbers that differ from x by a rational number plus an even multiple of \sqrt2 and numbers that differ from x by a rational number plus an odd multiple of \sqrt2. This alternation prevents G from containing any cycles of odd length, so each of its finite subgraphs requires only two colors. However, in the
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 (ZF) hold, exclusive of the axiom of choice, but in which all sets of real numbers are Lebesgue measu ...
in which every set of real numbers is
Lebesgue measurable In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides wit ...
, 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).


Generalizations

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 \chi of all of V with the property that every finite set S has a finite superset T on which \chi 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. 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 In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
as a subgraph. However, they may have arbitrarily large
odd girth In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity. For example, a 4-cycle (square) h ...
, and therefore they may avoid any finite set of non-bipartite subgraphs. The De Bruijn–Erdős theorem also applies directly to
hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
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 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. This theorem is an important tool in model theory, as it provides a useful (but generally no ...
of
Kurt Gödel Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imme ...
, stating that a set of
first-order In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
sentences has a
model A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
if and only if every finite
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of it has a model. More specifically, the De Bruijn–Erdős theorem can be interpreted as the compactness of the first-order
structures A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
whose non-logical values are any finite set of colors and whose only predicate on these values is inequality. The theorem may also be generalized to situations in which the number of colors is an infinite
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
. If \kappa is a
strongly compact cardinal In set theory, a branch of mathematics, a strongly compact cardinal is a certain kind of large cardinal. A cardinal κ is strongly compact if and only if every κ-complete filter can be extended to a κ-complete ultrafilter. Strongly compact cardi ...
, then for every graph G and cardinal number \mu<\kappa, G has chromatic number at most \mu if and only if each of its subgraphs of cardinality less than \kappa has chromatic number at most \mu.This follows immediately from the definition of a strongly compact cardinal \kappa as being a cardinal such that every collection of formulae of
infinitary logic An infinitary logic is a logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how c ...
each of length smaller than \kappa, that is satisfiable for every subcollection of fewer than \kappa formulae, is globally satisfiable. See e.g. .
The original De Bruijn–Erdős theorem is the case \kappa=\aleph_0 of this generalization, since a set is finite if and only if its cardinality is less than \aleph_0. However, some assumption such as the one of being a strongly compact cardinal is necessary: if the
generalized continuum hypothesis In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that or equivalently, that In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
is true, then for every infinite cardinal \gamma, there exists a graph G of cardinality (2^\gamma)^+ such that the chromatic number of G is greater than \gamma, but such that every subgraph of G whose vertex set has smaller power than G has chromatic number at most \gamma. 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


References

*. *. *. *. *. *. *. *. *. *. *. *. *. *. * *. *. *. *. *. *. *. *. *. *. 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. {{DEFAULTSORT:De Bruijn-Erdos theorem (graph theory) Graph coloring Infinite graphs Theorems in graph theory Axiom of choice Paul Erdős