De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs

Statement

De Bruijn–Erdős theorem (N. G. de Bruijn & P. Erdős, "A colour problem for infinite graphs and a problem in the theory of relations," *Indagationes Mathematicae* 13 (1951), 369–373; en.wikipedia.org/wiki/De_Bruijn–Erdős_theorem_(graph_theory)):

> Let $G=(V,E)$ be a graph (of any cardinality) and $d$ a natural number. If every finite subgraph $H$ of $G$ satisfies $\chi(H)\le d$, then $\chi(G)\le d$.

Equivalently: $G$ is $d$-colourable iff every finite subgraph of $G$ is $d$-colourable. (The "only if" direction is trivial — a proper colouring of $G$ restricts to a proper colouring of any subgraph; the theorem is the nontrivial "if" direction.) Consequently, if $\chi(G)=\infty$ (no finite $d$ works globally), $G$ must contain finite subgraphs of every finite chromatic number $1,2,3,\dots$ — there is no way to have "genuinely infinite, non-finitary" chromatic obstruction; all the obstruction is already witnessed finitely.

A slightly more refined form, closer to how it is actually deployed: for any $d$ and any graph $G$, $\chi(G)\le d$ iff every finite induced subgraph of $G$ has a proper $d$-colouring — and by König's-lemma-style bookkeeping, one can even demand only that arbitrarily large finite subgraphs be $d$-colourable (Nash-Williams 1967 phrasing via the infinity lemma).

Facts

- Original source: de Bruijn & Erdős (1951), Indag. Math. 13, 369–373 (mathworld.wolfram.com/deBruijn-ErdosTheorem.html). Not to be confused with the *other* "de Bruijn–Erdős theorem" by the same two authors — the 1948 incidence-geometry result "every noncollinear set of $n$ points in the plane determines at least $n$ lines" (Indag. Math. 10 (1948), 421–423) — a different theorem, same author pair, same year-adjacent papers, frequently cross-linked/confused in the literature. - It is a compactness theorem in the logical sense: "$G$ is $d$-colourable iff every finite subgraph is" is exactly an instance of the compactness theorem for first-order/propositional logic — encode "vertex $v$ gets colour $i$" as a Boolean/propositional variable $x_{v,i}$, encode "at least one colour per vertex" and "adjacent vertices differ" as clauses; a global proper colouring exists iff this (possibly infinite) set of clauses is satisfiable, and by propositional compactness that holds iff every finite subset of clauses (equivalently every finite subgraph's constraints) is satisfiable. This is the cleanest way to see WHY it is true and is the standard modern proof route (see en.wikipedia.org/wiki/De_Bruijn–Erdős_theorem_(graph_theory); arxiv.org/pdf/1609.05221 "Logical compactness and constraint satisfaction problems" develops this CSP-compactness view generally). - All known proofs use some form of the Axiom of Choice, and this is *necessary*, not incidental: - Gottschalk (1951), "Choice functions and Tychonoff's theorem," *Proc. AMS* — proves it via Tychonoff's theorem applied to the compact product space $\{1,\dots,d\}^V$ (product topology, each finite factor discrete hence compact): the set of colourings respecting each single edge-constraint is closed, the family of all such closed sets (one per edge, or one per finite subgraph's constraint-conjunction) has the finite intersection property exactly because every finite subgraph is $d$-colourable, so by compactness of the product (Tychonoff) the intersection over *all* edges is nonempty — any point in it is a global proper $d$-colouring. - Zorn's-lemma / direct extension arguments (Pósa, Dirac, per Wikipedia's proof-list) build the colouring by transfinite/Zorn extension over an exhaustion of $V$ by finite pieces. - Ultrafilter proofs (Luxemburg 1962; sketch also in pointatinfinityblog.wordpress.com/2017/01/10/ultrafilters-viii-chromatic-compactness): put an ultrafilter on the directed set of finite subgraphs (ordered by inclusion) that concentrates on "arbitrarily large" finite pieces; each finite subgraph $H$ has *some* proper $d$-colouring $c_H$ by hypothesis; for each vertex $v$ take the ultrafilter-limit of $c_H(v)$ over all finite $H\ni v$ — since there are only $d$ (finitely many) possible colour values, the ultrafilter forces a single limiting colour per vertex, and this glued assignment is automatically a proper colouring of all of $G$ because every single edge is already checked inside cofinally many finite $H$. - Non-standard analysis (Hurd & Loeb 1985): take a $*$-finite subgraph containing all of $V$ (via an ultrapower/nonstandard extension) that is internally $d$-colourable (transfer principle), then push the internal colouring back down to a standard colouring of $G$. - König's infinity-lemma route (Nash-Williams 1967) — works directly for countable $G$: build a tree of "consistent partial finite $d$-colourings," each level extending by one more vertex, argue every level is nonempty (by hypothesis) and the tree is finitely branching, so König's lemma gives an infinite branch = colouring of all of $V$. This is the most "elementary" (no explicit AC beyond countable choice) special case and a good first proof to internalize before the general uncountable statement. - Rado's selection lemma (R. Rado, "Axiomatic treatment of rank in infinite sets," *Bull. AMS* 55 (1949)) is a genuine generalization, not just another proof: given an infinite index set $V$ and, for every finite subset $S\subseteq V$, *some* choice of a function $C_S:S\to$ (finite colour set), there exists a single global $\chi:V\to$ (colour set) such that every finite $S$ has a finite superset $T\supseteq S$ with $\chi|_T = C_T$. Applying this with $C_S$ = "the" proper colouring of the induced subgraph on $S$ recovers de Bruijn–Erdős as a corollary; Rado's lemma is the reusable abstract "glue compatible finite choices into one global choice" engine. - Exact logical strength: the theorem is strictly weaker than full AC and is provably equivalent to the Boolean Prime Ideal theorem (BPI) (equivalently, to the compactness theorem for propositional logic / existence of ultrafilters extending filters): Mycielski (1961) showed BPI $\Rightarrow$ theorem; Läuchli (1971), "Coloring infinite graphs and the Boolean prime ideal theorem," *Fund. Math.*, closed the loop by showing the theorem (even restricted to $d=3$, i.e. compactness of $K_3$-colourability) $\Rightarrow$ BPI. So in the Zoo-of-choice-principles sense, de Bruijn–Erdős compactness sits exactly at the BPI level — strictly between ZF and ZF+AC. - Generalization to infinite $d$ (Erdős & Hajnal, 1966/1968 — cited on Wikipedia) and to infinite colour-cardinalities/partition relations more broadly; also Chen & Chvátal, "Problems related to a de Bruijn–Erdős theorem," *Discrete Appl. Math.* 156 (2008), 2101–2108 (a *different, geometric* line-cover generalization inspired by the 1948 theorem's name, not the chromatic one — flag the name-collision when citing). - Sharpest headline use-case: reduces the Hadwiger–Nelson problem ("what is the chromatic number of the plane, i.e. of the infinite unit-distance graph on $\mathbb{R}^2$?" — erdos/508) from an a-priori infinitary question to a purely finite one: $\chi(\mathbb{R}^2)\ge k$ iff *some finite* unit-distance graph has $\chi\ge k$ — which is exactly how the current best lower bound (de Grey 2018, $\chi\ge5$, via an explicit 1581-vertex finite unit-distance graph) is a legitimate proof about the *infinite* plane despite being a finite combinatorial/SAT computation.

Technique

When it applies: any situation where you must determine (or bound) the chromatic number of an infinite structure — an infinite graph, an infinite-vertex geometric graph (unit-distance graphs, distance graphs on $\mathbb{R}^n$, Cayley graphs of infinite groups), or more generally any "colour subject to local constraints" problem that can be phrased as "assign one of $d$ labels to each element of a (possibly infinite) index set, subject to a family of finitary forbidden-pattern constraints." Also applies verbatim to related finitary-constraint structures: infinite partial orders (Dilworth's theorem extended to infinite posets), infinite planar graphs (four-colour theorem extended from finite planar maps to *all* planar graphs, since planarity and the 4-colourability obstruction are both finitely testable), and more generally any class closed under finite subgraphs where the finite case is already solved/bounded.

Why it works (the mechanism): chromatic-number-$\le d$ is a local, finitely-checkable property that only degrades monotonically — adding more vertices/edges to a graph can only keep $\chi$ the same or increase it, never decrease it below what's forced by a finite piece, AND a colouring of the whole graph restricts consistently to every piece. This "monotone + locally finitary + restriction-consistent" shape is exactly what the compactness theorem of logic captures: encode the global colouring as a model of an (infinite) set of first-order/propositional constraints, note that unsatisfiability would already show up in some finite conjunction of constraints (since each constraint mentions only finitely many vertices — an edge only involves 2), hence "no finite obstruction" $\Rightarrow$ "no obstruction at all." The Axiom of Choice (or the strictly weaker BPI) is exactly the ingredient needed to convert "every finite piece has *a* solution" into "there is *one* solution simultaneously compatible with all finite pieces" when there are infinitely many pieces and no canonical/constructive way to pick compatible colourings — this is the general pattern (Tychonoff / ultrafilter-limit / Rado-selection are three equivalent packagings of the same "take a coherent limit over finite approximations" idea).

How to actually use it to attack a new instance (recipe): 1. Phrase the infinite target (unit-distance graph on $\mathbb{R}^n$, Cayley graph of an infinite group, infinite poset, etc.) as a graph/relational structure where every constraint (edge, comparability, forbidden pattern) involves only finitely many elements. 2. To prove a lower bound $\chi(G)\ge k$: it suffices to exhibit one finite subgraph $H\subseteq G$ with $\chi(H)\ge k$ — turns an infinitary existence claim into a finite, often computer-searchable/SAT-solvable, combinatorial construction (this is exactly the de Grey / Hadwiger–Nelson play, erdos/508). 3. To prove an upper bound $\chi(G)\le d$: it suffices to show every finite subgraph is $d$-colourable — often provable by a finite/local structural argument (e.g. a bounded-degree or bounded-density condition implying $d$-colourability via a greedy/degeneracy bound applied to any finite piece), then invoke de Bruijn–Erdős to lift it to the whole (possibly infinite) graph automatically, with no separate infinite construction needed. 4. If the setting is countable, prefer the König's-infinity-lemma proof (Nash-Williams route) for a lighter-weight, more constructive-feeling argument; for uncountable settings, the Tychonoff/ultrafilter/Rado-selection routes are the standard tools, and genuinely require BPI-strength choice — flag this if the surrounding proof is meant to be choice-free or the base theory is ZF-only. 5. Watch for the reverse move: if a finite-chromatic-number classification/characterization is *itself* open or hard (e.g., the exact value of $\chi(\mathbb{R}^2)$), de Bruijn–Erdős does NOT resolve it — it only certifies that the eventual finite witness graphs (once found) constitute a full proof; it does not help *find* them.

Related

- erdos/508 — Hadwiger–Nelson problem (chromatic number of the plane): the theorem's flagship live application, reducing an infinite geometric colouring question to finite unit-distance-graph constructions (de Grey 2018, $\chi\ge5$). - Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou) — a different chromatic-number technique (concentration/anti-concentration of $\chi$ across random or structured graph families); complementary finite-graph machinery that can supply the finite witness graphs step 2 above calls for. - Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs — one of the standard tools for proving the *finite*-subgraph upper bound (step 3) that de Bruijn–Erdős then lifts to the infinite structure, as in the four-colour-theorem-for-infinite-planar-graphs application. - Additive-energy / pigeonhole averaging identity — $\sum_n r_A(n)=|A|^2$ forces large representation values on the dense side — another common finite-side tool for bounding $\chi(H)$ on finite pieces before invoking compactness.