Teorema de los cuatro colores
En matemáticas , el teorema de los cuatro colores , o el teorema del mapa de cuatro colores , establece que no se requieren más de cuatro colores para colorear las regiones de cualquier mapa de modo que no haya dos regiones adyacentes con el mismo color. Adyacente significa que dos regiones comparten un segmento de curva de límite común, no simplemente una esquina donde se encuentran tres o más regiones. [1] Fue el primer teorema importante que se demostró utilizando una computadora . Inicialmente, esta prueba no fue aceptada por todos los matemáticos porque la prueba asistida por computadora no era factible para que un humano la verificara a mano . [2]Desde entonces, la prueba ha ganado una amplia aceptación, aunque quedan algunos escépticos. [3]
El teorema de los cuatro colores fue probado en 1976 por Kenneth Appel y Wolfgang Haken después de muchas pruebas falsas y contraejemplos (a diferencia del teorema de los cinco colores , probado en el siglo XIX, que establece que cinco colores son suficientes para colorear un mapa). Para disipar cualquier duda restante sobre la prueba de Appel-Haken, Robertson, Sanders, Seymour y Thomas publicaron en 1997 una prueba más simple que usaba las mismas ideas y aún confiaba en las computadoras. En 2005, el teorema también fue probado por Georges Gonthier con un software de demostración de teoremas de propósito general .
En términos de la teoría de grafos, el teorema establece que para un grafo plano sin bucle , su número cromático es .
La declaración intuitiva del teorema de los cuatro colores - "dada cualquier separación de un plano en regiones contiguas, las regiones se pueden colorear usando como máximo cuatro colores para que no haya dos regiones adyacentes con el mismo color" - debe interpretarse adecuadamente para que sea correcta .
Primero, las regiones son adyacentes si comparten un segmento de límite; dos regiones que comparten solo puntos de límite aislados no se consideran adyacentes. En segundo lugar, las regiones extrañas, como las que tienen un área finita pero un perímetro infinitamente largo, no están permitidas; los mapas con tales regiones pueden requerir más de cuatro colores. [4] (Para estar seguros, podemos restringir a las regiones cuyos límites consisten en un número finito de segmentos de línea recta. Se permite que una región rodee por completo una o más regiones). Tenga en cuenta que la noción de "región contigua" (técnicamente: subconjunto abierto conectado del plano) no es el mismo que el de un "país" en los mapas regulares, ya que los países no necesitan ser contiguos (por ejemplo, la provincia de Cabinda como parte de Angola ,Nakhchivan como parte de Azerbaiyán , Kaliningrado como parte de Rusia y Alaska como parte de los Estados Unidos no son contiguas). Si exigimos que todo el territorio de un país reciba el mismo color, entonces cuatro colores no siempre son suficientes. Por ejemplo, considere un mapa simplificado:
En este mapa, las dos regiones etiquetadas como A pertenecen al mismo país. Si quisiéramos que esas regiones recibieran el mismo color, entonces se necesitarían cinco colores, ya que las dos regiones A juntas son adyacentes a otras cuatro regiones, cada una de las cuales es adyacente a todas las demás. Forzar dos regiones separadas para que tengan el mismo color se puede modelar agregando un 'mango' que las une fuera del plano.
