Sea $G$ sea un grafo infinito, tal que todo subgrafo finito de $G$ puede colorearse con $k$ colores. ¿Es necesario que $G$ puede colorearse con $k$ ¿Colores?
La respuesta es sí, y para demostrarlo empezaremos definiendo una topología sobre el espacio de todas las coloraciones de $G$ .
Sea $V$ sea el conjunto de vértices de $G$ . Una coloración de $G$ - no necesariamente legal - es sólo una función $f : V \to A$ donde $A$ es el conjunto finito de $k$ colores. Denotemos el espacio de todas las coloraciones por $X$ .
Podemos topologizar $X$ tomando un conjunto abierto básico de la forma $U_{v,c}$ donde $v$ es un vértice de $G$ , $c$ es algún color en $A$ y $U_{v,c}$ es el conjunto de esas coloraciones $f \in X$ tal que $f(v)=c$ . Un poco de pensamiento revela que esto es sólo el espacio producto espacio $A^V$ donde $A$ recibe la topología discreta.
Hay un teorema muy poco trivial de Tychonoff que dice que el producto de espacios compactos vuelve a ser compacto. Así que el espacio $X$ es compacto. Esto implica que toda colección de subconjuntos cerrados de $X$ con la propiedad de intersección finita (la intersección de un número finito de conjuntos de la colección es no vacía) tiene una intersección no vacía.
Sea $H$ sea un subgrafo finito de $G$ . Si $f$ es una coloración de $G$ podemos obtener una coloración de $H$ restringiendo $f$ al conjunto de vértices de $H$ . Por supuesto, si $f$ fueran una coloración válida de $G$ restringiéndolo a $H$ da una coloración válida de $H$ - en $H$ hay menos vértices y aristas de los que preocuparse.
A la inversa $f$ sea una coloración de $G$ y supongamos que al restringir $f$ a cada subgrafo finito de $G$ da una coloración válida. Afirmo que $f$ es una coloración válida de $G$ también. Supongamos que no. Entonces hay vértices $u,v$ conectadas por una arista tal que $f(u) = f(v)$ . Pero entonces la restricción de $f$ al subgrafo finito $H$ que consta de los vértices $u,v$ y el borde entre ellos, no es una coloración legal. Esto contradice nuestra suposición inicial.
Así que vamos a encontrar una coloración de $f$ de $G$ cuya restricción a cada subgrafo finito es legal y esto demostrará nuestro teorema.
Si $H$ es un subgrafo finito de $G$ , dejemos que $C_H$ denota el conjunto de aquellas coloraciones de $G$ cuya restricción a $H$ es legal. Por hipótesis $C_H$ no es vacío para cada $H$ . Además, el conjunto $C_H$ está cerrado. Porque si $f$ es una coloración de $G$ que se encuentra fuera $C_H$ entonces hay vértices $u,v$ de $H$ conectadas por una arista en $H$ tal que $f(u) = f(v)$ . El conjunto de $U$ de esos $g$ que coinciden con $f$ en $u,v$ está abierto y contiene $f$ pero es disjunta de $C_H$ (no hay tal $g$ puede ser válida si se limita a $H$ ). De ello se deduce que $C_H$ es cerrado, ya que su complemento contiene una vecindad de cada uno de sus puntos.
Por último, la familia ${C_H}$ goza de la propiedad de intersección finita: si $H_1, ..., H_n$ son subgrafos finitos, entonces una coloración válida de su unión es una coloración válida de cada uno de ellos individualmente. Por tanto, $C_{H_1 \cup ... \cup H_n}$ es un subconjunto no vacío de $C_{H_1} \cap ... C_{H_n}$ .
Por compacidad, la intersección de todas las $C_H$ para $H$ un subgrafo finito, no es vacío. Si $f$ es un elemento de la intersección, entonces es una coloración válida de cada subgrafo finito por definición, y por lo tanto, por lo anterior, una coloración válida de $G$ .
La demostración anterior es muy similar a la demostración de que el teorema de la compacidad en topología da lugar al teorema de la compacidad para el cálculo proposicional; por tanto, la compacidad lógica y topológica son nociones distintas, pero relacionadas.