De Bruijn–Erdős theorem (graph theory)

A graph is k-colorable if and only if each of its finite subgraphs is k-colorable, for every finite k. The theorem extends finite coloring obstructions to arbitrary graphs.

Connect

Compactness theorem: A first-order theory has a model if every finite subset of its sentences has a model. Graph coloring can be encoded as a first-order theory, so logical compactness yields the theorem.
Graph coloring: An assignment of colors to graph vertices, with adjacent vertices receiving different colors. The theorem concerns when a coloring with a fixed finite palette exists.
N. G. de Bruijn: Dutch mathematician Nicolaas Govert de Bruijn, known for work in combinatorics, number theory, and analysis. He co-authored the graph-coloring theorem in 1951.
Infinite chromatic number: A graph has infinite chromatic number when no finite number of colors suffices for a proper coloring. If a graph has infinite chromatic number, some finite subgraph already requires more than any specified finite palette.
Compactness principle: A principle that a global object exists when every finite collection of its constraints can be satisfied. The theorem is a concrete graph-theoretic illustration of this local-to-global pattern.
Finite intersection property: A family of sets has this property when every finite subfamily has nonempty intersection. Coloring constraints on finite vertex sets must remain jointly satisfiable.
Proper vertex coloring: A vertex coloring in which the endpoints of every edge have different colors. This is the precise condition that each finite subgraph must satisfy.
Paul Erdős: Hungarian mathematician Paul Erdős, a prolific contributor to combinatorics and graph theory. He co-authored the theorem with de Bruijn.
Odd cycle: A cycle containing an odd number of edges. An odd cycle is a finite obstruction to two-colorability, so it also obstructs two-colorability in any graph containing it.
Critical graph: A graph whose chromatic number drops when any vertex is removed. Minimal failures of k-colorability are finite by the theorem, hence include finite critical obstructions.