¿Existe algún resultado tipo el teorema de los cuatro colores en tres dimensiones?

El teorema de los cuatro colores asegura que todo mapa plano puede colorearse con, a lo sumo, cuatro colores de forma que regiones con frontera común tengan colores distintos. Atentos: mapa plano. Es decir, un mapa que se pueda dibujar en un plano, en dos dimensiones (*). ¿Y qué ocurre si subimos una dimensión? Esto es, ¿existe algún resultado tipo el teorema de los cuatro colores para mapas formados por regiones tridimensionales?

Pues la respuesta es que no existe una cota para el número de colores necesario para colorear un mapa de regiones tridimensionales de forma que dos regiones con frontera común tengan colores distintos. Es decir, se pueden construir mapas de regiones tridimensionales para los cuales haga falta una cantidad de colores igual a un número natural cualquiera. Y la razón vuelve a estar, como en el caso del teorema para mapas planos, en la teoría de grafos.

Como ya vimos en la entrada de ayer sobre el teorema de los cuatro colores, todo mapa plano es equivalente a un grafo plano en el que cada vértice corresponde con una región del mapa inicial y en el que una arista una dos vértices representa que en el mapa inicial esas dos regiones tenían frontera común. Pero en general esa equivalencia se tiene con cualquier mapa, hasta con los tridimensionales, aunque en ese caso el grafo puede no ser plano. Por tanto en vez de un mapa tridimensional consideremos su grafo asociado.

La cuestión clave de este asunto es que cualquier grafo (plano o no) se puede representar en el espacio tridimensional de manera que no haya dos aristas que se corten en algún punto que no sea un vértice (esta propiedad se suele expresar diciendo que todo grafo es realizable en el espacio tridimensional). Entonces, por poner un par de ejemplos, los grafos completos son realizables en tres dimensiones (pero si tiene cinco o más vértices no lo son en dos dimensiones, es decir, no son planos). Un grafo completo, que suele representarse como , es un grafo con vértices que cumple que cada vértice está unido con todos los demás con una arista. Por ejemplo, aquí tenéis a y a :

Si nos fijamos, por ejemplo, en vemos que el hecho de que cada vértice esté unido con los otros cuatro nos obliga a utilizar cinco colores para colorear sus vértices (si usamos menos siempre habría al menos dos vértices conectados con una arista que tendría el mismo color). ¿Y cuántos hacen falta para ? Pues, por la misma razón, nos harán falta seis colores. En general, para colorear los vértices de de la forma descrita antes se necesitan colores. Por tanto no hay cota del máximo número de colores necesarios para colorear los vértices de un grafo en tres dimensiones, y por tanto ocurre lo mismo con un mapa tridimensional. Asunto resuelto.

Con colores todo queda mucho mejor

Vale, sí, asunto resuelto, pero con colores todo queda mucho mejor, ¿verdad? Estamos todos de acuerdo en que usando grafos queda todo demostrado, pero si vemos el mapa tridimensional con sus colores seguro que nos quedara más claro. Pues vamos a ello. Vamos a ver un ejemplo que Claudi Alsina plantea en su libro Mapas del metro y redes neuronales en el que se ve que se pueden construir mapas tridimensionales para los cuales hagan falta tantos colores como un número natural cualquiera.

La construcción se va a hacer en forma de sucesión de conjuntos: construiremos uno para el que necesitamos un color, a partir de ése construiremos otros para el que hacen falta dos colores, y así sucesivamente. El primero de ellos va a ser una pieza cúbica, un cubo. Para pintarlo necesitamos un único color (usamos el amarillo). Le pegamos otro cubo al inicial y obtenemos el segundo conjunto. Ahora necesitamos dos colores (usamos el amarillo inicial y el naranja para el nuevo cubo). Y el tercero se obtiene pegándole a esos dos cubos una pieza como la que se ve pintada de azul a la derecha en la imagen siguiente (donde también aparecen los dos primeros conjuntos):

En ese tercer conjunto, como la pieza que añadimos tiene frontera común con las otras dos tenemos que se necesitan tres colores. Colocamos ahora una nueva pieza como aparece en la siguiente figura pintada de verde:

Necesitamos un nuevo color porque dicha pieza «toca» a las tres anteriores. Ya tenemos un mapa que necesita cuatro colores. Para construir uno que necesite cinco hacemos lo siguiente: duplicamos el mapa que necesita cuatro y lo pegamos debajo de ese mismo mapa por las partes verdes (que pasarán a ser una única pieza). Después añadimos una pieza tipo la verde anterior. La cosa queda más o menos así:

La pieza que acabamos de añadir está en contacto con todas las anteriores, por lo que debe ir en un color distinto a los que teníamos ya (gris en este caso). Ya tenemos uno que necesita cinco colores.

Y siguiendo de la misma forma (duplicamos el mapa anterior, pegamos por las partes correspondientes a la última pieza que se añadió y se coloca una nueva pieza que tiene parte común con todas las anteriores) obtenemos mapas que van necesitando cada vez más colores. El que necesita seis colores quedaría así:

En él hemos pintado la nueva pieza de color dorado. Y el que necesita siete colores (con la nueva pieza en rosa) queda de la siguiente forma:

Con este procedimiento podemos construir mapas tridimensionales que necesitan una cantidad cualquiera de colores para colorearlos de forma que regiones con frontera común tengan colores distintos. Por tanto no hay cota para el número máximo de colores necesarios para ello.

(*) En un plano…o en una esfera tridimensional, ya que cualquier mapa dibujado en una esfera en tres dimensiones tiene su equivalente en dos dimensiones a través de la proyección estereográfica.

Quinta aportación a la Edición 4.123 del Carnaval de Matemáticas, que organiza el blog Eulerianos.