Teorema de de Bruijn-Erdős

Demonstração (para grafos enumeráveis): 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 um grafo arbitrário): Sejam $S := \{1, \ldots, k\}$ e $\mathcal F$ a coleção de todos os subconjuntos finitos de $V$. Para cada $Y \in F$, seja $\mathcal A (Y)$ o conjunto das $k$-colorações de $G[Y]$. Seja $\mathcal Y \subseteq \mathcal F$. Tomemos uma $k$-coloração do grafo finito $G[\bigcup \mathcal Y]$. Podemos encontrar uma função $V \to \{1, \ldots, k\}$ que induz coloração em $G[Y]$ para todo $Y \in \mathcal Y$. Pelo princípio da compacidade, induzimos uma $k$-coloração em $G$.