Gráfico de Errera

El teorema de los cuatro colores afirma que los vértices de todo grafo planar pueden colorearse con cuatro colores, de manera que no haya dos vértices adyacentes con el mismo color. Alfred Kempe publicó una demostración errónea en 1879 , pero se descubrió su error en 1890. El teorema de los cuatro colores no tuvo una demostración válida hasta 1976. La demostración de Kempe puede traducirse en un algoritmo para colorear grafos planares, que también es erróneo. Se encontraron contraejemplos a su demostración en 1890 y 1896 (el grafo de Poussin ), y posteriormente, el grafo de Fritsch y el grafo de Soifer proporcionaron dos contraejemplos menores. ^{[ 3 ]} Sin embargo, hasta el trabajo de Errera, estos contraejemplos no demostraron que todo el algoritmo de coloración fallara. Más bien, asumieron que todos los vértices del grafo, excepto uno, ya estaban coloreados, y demostraron que el método de Kempe (que supuestamente modificaría la coloración para extenderla a todo el grafo) fallaba en esas instancias precoloreadas. El grafo de Errera, por otro lado, proporciona un contraejemplo para todo el método de Kempe. Cuando este método se ejecuta en el grafo de Errera, comenzando sin vértices coloreados, puede fallar al encontrar una coloración válida para todo el grafo. ^{[ 1 ]} Además, a diferencia del grafo de Poussin, todos los vértices en el grafo de Errera tienen grado cinco o más. Por lo tanto, en este grafo, es imposible evitar los casos problemáticos del método de Kempe eligiendo vértices de menor grado.

La figura muestra un ejemplo de cómo la demostración de Kempe puede fallar para este grafo. En la figura, las adyacencias entre regiones de este mapa forman el grafo de Errera, parcialmente coloreado con cuatro colores, con la región exterior sin colorear. La demostración errónea de Kempe sigue la idea de extender coloraciones parciales como esta mediante el recoloreado de cadenas de Kempe , subgrafos conexos que tienen solo dos colores. Cualquier cadena de este tipo puede recolorearse, conservando la validez de la coloración, intercambiando sus dos colores en todos los vértices de la cadena. La demostración de Kempe presenta diferentes casos dependiendo de si el siguiente vértice a colorear tiene tres, cuatro o cinco vecinos y de cómo se colorean esos vecinos. En el caso mostrado, el siguiente vértice a colorear es el que corresponde a la región exterior del mapa. Esta región no puede colorearse directamente, porque ya tiene vecinos de los cuatro colores diferentes. Los vecinos azul y amarillo están conectados por una única cadena de Kempe (mostrada por las líneas amarillas discontinuas en la imagen), lo que impide que un intercambio los convierta ambos en azules o ambos en amarillos y libere un color. De manera similar, los vecinos azul y verde están conectados por otra cadena de Kempe (las líneas verdes discontinuas). En tal caso, la demostración de Kempe intentaría intercambiar simultáneamente los colores en dos cadenas de Kempe: la cadena rojo-amarilla izquierda y la cadena rojo-verde derecha (líneas rojas discontinuas). La cadena azul-verde impide que la cadena rojo-amarilla izquierda llegue al lado derecho del gráfico, y la cadena azul-amarilla impide que la cadena rojo-verde derecha llegue al lado izquierdo, por lo que parecería que intercambiar simultáneamente los colores en estas dos cadenas es una operación segura. Pero debido a que las cadenas azul-amarilla y azul-verde se cruzan en lugar de permanecer separadas, hay una región en el centro de la figura donde las cadenas rojo-amarilla y rojo-verde pueden encontrarse. Cuando estas dos cadenas se encuentran en el medio, el intercambio simultáneo provoca que los vértices amarillos y verdes adyacentes en esta área central (como los vértices representados por las regiones amarillas y verdes superiores en la figura) se vuelvan rojos, produciendo una coloración no válida.

La teoría de grafos químicos se ocupa de la estructura basada en la teoría de grafos de las moléculas y otros grupos de átomos. Tanto el grafo de Errera como su grafo dual son relevantes en este contexto.

Los átomos de metales como el oro pueden formar cúmulos en los que un átomo central está rodeado por doce átomos más, siguiendo el patrón de un icosaedro . Otro tipo de cúmulo, de mayor tamaño, se puede formar mediante la coalescencia de dos de estos cúmulos icosaédricos, de modo que el átomo central de cada cúmulo se convierte en uno de los átomos límite del otro. El cúmulo resultante de 19 átomos tiene dos átomos internos (los centros de los dos icosaedros) con 17 átomos en la capa externa, siguiendo el patrón del grafo de Errera. ^{[ 4 ]}

El grafo dual del grafo de Errera es un _fullereno [ ^{1 ] con} 30 vértices, designado en la literatura química como C30 ₍ D5h ₎ [ ^{5 ] o} F30 ₍ D5h ₎ [ ^{6 ] para} _{indicar su simetría y distinguirlo de otros fullerenos de} 30 vértices. Esta forma también desempeña un papel central en la construcción de fullerenos de dimensiones superiores. ^{[ 6 ]}