De Bruijn–Erdős theorem (graph theory)
In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), states that the chromatic number of an infinite graph, if this number is finite, is the same as the largest chromatic number of any of its finite subgraphs. According to this theorem, an infinite graph G can be colored by k colors (for finite k, with no two adjacent vertices having the same color) if and only if all of its finite subgraphs can be colored by k colors. Equivalently, every k-critical graph (a graph that requires k colors but for which all subgraphs require fewer colors) must have a finite number of vertices.
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 partial orders to infinite ones, and reducing the Hadwiger–Nelson problem on the chromatic number of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose cardinality is a strongly compact cardinal.
The original proof by De Bruijn used transfinite induction.
Gottschalk (1951) provided the following very short proof, based on Tychonoff's compactness theorem 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 viewed as a product space kV(G) which by Tychonoff's theorem is compact. For each finite subgraph F of G, let XF be the subset of X consisting of assignments of colors that validly color F. Then the system of sets XF is a family of closed sets with the finite intersection property, so by compactness it has a nonempty intersection. Every member of this intersection is a valid coloring of G.
...
Wikipedia