====== Teorema de de Bruijn-Erdős ======

=== Sejam $G =(V, E)$ um grafo e $k \in \mathbb{N}$. Se todo subgrafo finito de $G$ possuir um número cromático até $k$, então $G$ também o possui. ===

----

//Demonstração// **(para grafos enumeráveis)**: Seja $v_0, v_1, ...$ uma indexação de $V$ e definamos o grafo induzido $G_n := G[v_0, ..., v_n]$. Agora, seja $V_n$ o conjunto de todas as $k$-colorações de $G_n$ com cores em $\{1, ..., 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, ..., v_{n-1}\}$. Pelo [[grafos:koniginfinity|Lema da Infinitude de König]], podemos tomar o raio $c_0 c_1 ...$ 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, ..., k\}$.

----

//Demonstração// **(para um grafo arbitrário)**: Sejam $S := \{1, ..., 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, ..., 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$.