Teorema de de Bruijn-Erdős

Demonstração (para $G$ enumerável): Seja $v_0, v_1, \ldots$ uma indexação de $V$ e definamos o grafo induzido $G_n := G[v_0, \ldots, v_n]$. Agora, seja $V_n$ o conjunto de todas as $k$-colorações de $G_n$ com cores em $\{1, \ldots, k\}$. Podemos definir um novo grafo $C$ sobre $\bigcup_{n \in \mathbb N} V_n$: os vértices são colorações e as arestas são da forma $c c'$ com $c \in V_n$ e $c' \in V_{n-1}$ — a restrição de $c$ a $\{v_0, \ldots, v_{n-1}\}$. Pelo Lema da Infinitude de König, podemos tomar o raio $c_0 c_1 \ldots$ nesse grafo $C$ com $c_n \in V_n$ para todo $n \in \mathbb N$. Desse modo, temos que $c := \bigcup_{n \in \mathbb N} c_n$ é uma coloração de $G$ com cores em $\{1, \ldots, k\}$.

Demonstração (para $G$ arbitrário):