En teoría de grafos, el teorema de los cuatro colores (o teorema de la minimalidad cromática) es un teorema sobre la coloración de grafos que establece lo siguiente: Asumiendo que las regiones adyacentes comparten no solo un punto, sino todo un segmento de borde (frontera) en común. Tres colores son suficientes para mapas simples, pero en algunos casos es necesario un cuarto color adicional, esto es, cuando una región a colorear queda encerrada por un número impar de regiones que se tocan formando un ciclo. El teorema de los cinco colores, cuya demostración es corta y elemental, establece que cinco colores son suficientes para colorear un mapa y fue probado en el siglo XIX por Heawood. Una serie de pruebas falsas y falsos contraejemplos han aparecido desde el primer enunciado del teorema de los cuatro colores en 1852. El problema del mapa de cuatro colores fue planteado, por primera vez, por el estudiante Francis Guthrie en 1852, lo que fue comunicado a Augustus de Morgan. La conjetura se hizo famosa con la declaración de Arthur Cayley, en 1878, en el sentido de que la había abordado. Fue resuelto, a mediados de 1970, por Kenneth Appel y Wolfgang Haken.

Leer el artículo completo en Wikipedia · CC-BY-SA

In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are called adjacent if they share a common boundary that is not a corner, where corners are the points shared by three or more regions. Despite the motivation from coloring political maps of countries, the theorem is not of particular interest to mapmakers. According to an article by the math historian Kenneth May (, 2), “Maps utilizing only four colors are rare, and those that do usually require only three. Books on cartography and the history of mapmaking do not mention the four-color property.” Three colors are adequate for simpler maps, but an additional fourth color is required for some maps, such as a map in which one region is surrounded by an odd number of other regions that touch each other in a cycle. The five color theorem, which has a short elementary proof, states that five colors suffice to color a map and was proved in the late 19th century (); however, proving that four colors suffice turned out to be significantly harder. A number of false proofs and false counterexamples have appeared since the first statement of the four color theorem in 1852. Martin Gardner wrote a popular account of what was known at the time about the four color theorem in his September 1960 Mathematical Games column in Scientific American magazine. In 1975 Gardner revisited the topic by publishing a map said to be a counter-example in his infamous April fool's hoax column of April 1975. The four color theorem was proved in 1976 by Kenneth Appel and Wolfgang Haken. It was the first major theorem to be proved using a computer. Appel and Haken's approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem. (If they did appear, you could make a smaller counter-example.) Appel and Haken used a special-purpose computer program to confirm that each of these maps had this property. Additionally, any map that could potentially be a counterexample must have a portion that looks like one of these 1,936 maps. Showing this required hundreds of pages of hand analysis. Appel and Haken concluded that no smallest counterexamples exist because any must contain, yet do not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand (). Since then the proof has gained wider acceptance, although doubts remain (, 216–222). To dispel remaining doubt about the Appel–Haken proof, a simpler proof using the same ideas and still relying on computers was published in 1997 by Robertson, Sanders, Seymour, and Thomas. Additionally, in 2005, the theorem was proved by Georges Gonthier with general purpose theorem proving software.

Leer el artículo completo en Wikipedia · CC-BY-SA