¿Cómo puedo demostrarlo?
Si un gráfico $G$ es contable y si $a \in \mathbb{N}$ entonces $\chi(G) \leqslant a$ si y sólo si $\chi(S) \leqslant a$ para cada subgrafo finito $S$ .
Respuesta
¿Demasiados anuncios?
Este es el teorema de Bruijn-Erdős, y es un ejemplo de un compacidad argumento. No necesitamos la suposición de que $G$ es contable, pero hace que la prueba sea más elemental.
Se puede argumentar lo siguiente: (Estoy omitiendo algunos detalles menores.) Claramente, si $\chi(G)\le a$ entonces también $\chi(S)\le a$ para cualquier subgrafo finito $S$ .
A la inversa, enumerar los vértices de $G$ como $\{v_i\mid i\in\mathbb N\}$ . Fijar un conjunto $A$ de colores con $|A|=a$ . Si $a$ es infinito, no hay nada que demostrar, así que supongamos que es finito. Para cada $n$ , dejemos que $C_n$ sea el conjunto de coloraciones del subgrafo de $G$ con un conjunto de vértices $V_n:=\{v_1,\dots,v_n\}$ utilizando sólo los colores de $A$ . Tenga en cuenta que $C_n$ es no vacía, ya que estamos asumiendo que $\chi(S)\le a$ para cualquier subgrafo finito $S$ . Tenga en cuenta también que $C_n$ es finito, ya que una coloración es una función del conjunto $V_n$ de vértices a $A$ que satisface algunas condiciones, pero como $V_n$ y $A$ son finitas, sólo hay un número finito de tales funciones, independientemente de que satisfagan o no estas condiciones. Por último, hay que tener en cuenta que para cualquier $c\in C_m$ , si $m>n$ entonces la restricción de $c$ a $V_n$ está en $C_n$ .
Ahora se procede de forma recursiva: Ya que $C_1$ es finito, para algún $c_1\in C_1$ hay infinitos $m$ tal que existe una función $c\in C_m$ con $c\upharpoonright V_1=c_1$ . Desde $C_2$ es finito, se deduce que hay algún $c_2\in C_2$ tal que $c_2\upharpoonright V_1=c_1$ y para infinitos $m$ hay un $c\in C_m$ con $c\upharpoonright V_2=c_2$ . Desde $C_3$ es finito, se deduce que hay algún $c_3\in C_3$ tal que $c_3\upharpoonright V_2=c_2$ y para infinitos $m$ hay un $c\in C_m$ con $c\upharpoonright V_3=c_3$ . Etc.
Estas funciones $c_1,c_2,\dots$ son compatible en el sentido de que $c_i$ es sólo la restricción de $c_j$ a $V_i$ siempre que $i<j$ . Esto significa que podemos "parchearlos" para formar una función $c$ con dominio $\{v_i\mid i\in\mathbb N\}$ . La cuestión es que cada $c_i$ es una coloración con colores de $A$ y por lo tanto $c$ también lo es, porque si no hay vértices $v_i$ y $v_j$ con $i<j$ tal que $c(v_i)=c(v_j)$ y $\{v_i,v_j\}$ es una arista de $G$ . Pero por construcción, $c(v_j)=c_j(v_j)$ y $c(v_i)=c_i(v_i)=c_j(v_i)$ Así que $c_j$ no es una coloración del subgrafo de $G$ con un conjunto de vértices $V_j$ una contradicción.
Los argumentos de este tipo se llaman argumentos de compacidad porque pueden deducirse como corolarios de afirmaciones puramente topológicas sobre la compacidad de ciertos espacios; en este caso, la compacidad del producto contable de una familia de espacios finitos (discretos). La versión general de estos argumentos puede deducirse del teorema de compacidad de Tychonoff, y a veces se denomina principio de selección de Rado (aunque el teorema de Tychonoff es equivalente al axioma completo de elección, este principio es estrictamente más débil que él).
Truszczynski-Tuza y Rav escribieron un buen estudio de las aplicaciones de este resultado: Principio de selección de Rado: aplicaciones a relaciones binarias, coloraciones de grafos e hipergrafos y conjuntos parcialmente ordenados , Matemáticas Discretas, 103 , (1992), 301-312. MR1171783 (93j:05004) . Un caso muy conocido en el que el teorema de Bruijn-Erdős es relevante es el Problema de Hadwiger-Nelson sobre el número cromático del plano; nótese que este es un ejemplo en el que la versión contable del resultado no es suficiente.
