The four color theorem states that only four different colors are needed to color any map, such that any two regions sharing a common border have different colors. We've all seen a map painted that way, but as simple as it seems, formally determining which four colors suffice to color any map has kept the most important mathematicians busy for almost a century and a half. This is the story.
Often problems that seem too simple turn out to be a hard nut to crack when trying to obtain a mathematical proof or a generalization that covers all possible cases. The efficient coloring of maps is one of them, and it has given rise to the so-called 'four color theorem', which roughly states: "On a plane or on a sphere, no more than four colors are needed to color a map such that two adjacent regions, that is, regions sharing a border —a line, not a point— are not colored the same color."
You have surely seen many maps throughout your life, and regardless of their complexity, they have always shown the countries or regions they represent using only four different colors. Map makers and cartographers have known since the Renaissance that this number of colors was enough to avoid two neighboring states being painted the same color, but until the 19th century nobody believed that this system had anything to do with mathematics, and much less that a proof could be found confirming that it worked for any type or size of map.
The Problem Takes Shape
The four color issue only became a formal mathematical problem in the 1850s. The one who gave that 'category' to the problem faced by cartographers was an English student named Francis Guthrie, who intuited that the mechanism used could be proven. Since the problem exceeded his mathematical training, he discussed it with his brother Frederick, who had been a student of the prestigious English mathematician Augustus De Morgan.
Born in India in the early 1800s, De Morgan was the first president of the London Mathematical Society and tutor to the brilliant Ada Lovelace. He was also the author of the fundamental laws of the algebra of logic that bear his name ('The negation of a conjunction is equivalent to the disjunction of the negations' and 'The negation of a disjunction is equivalent to the conjunction of the negations'), so a priori he seemed the right person to prove this theorem, which was initially known as 'Guthrie's problem'. However, he could not do it.
The Quest Continues
Far from forgetting the problem his student had raised, De Morgan considered that 'the map coloring problem' was interesting enough to send a letter to his colleague Sir William Hamilton, who was famous for postulating the structure of quaternion numbers. Legend has it that one day in the early 1840s Hamilton was walking across Brongham Bridge, which crosses the Royal Canal in Dublin, and suddenly, in a moment of inspiration, he understood the structure of quaternions. He immediately carved the idea into a stone with his knife.
Quaternions would prove fundamental for building relativistic and quantum physics, and for proving Lagrange's theorem that any integer can be written as the sum of four perfect squares. Hamilton was at the peak of his career —he had not yet been affected by the alcohol addiction that would bury him in the mid-1860s— so De Morgan hoped he would be able to prove the 'four color theorem'. However, the mathematician never dealt with the problem, or he tried and could not solve it.
The First Attempts and Their Flaws
But De Morgan never forgot the matter, and he frequently mentioned it to other mathematicians. Some historians even believe he is actually the author of an anonymous article included in an issue from the early 1860s of the magazine Athenaeum that deals with the four color problem, which is considered the first published reference on this conjecture. By the early 1860s the theorem had already crossed the ocean, and several American mathematicians had started working to solve it.
The philosopher and scientist Charles Sanders Peirce was one of the first to tackle it on that continent. In the late 1870s, the mathematician Arthur Cayley published an article called 'On the colourings of maps', in which he presented the problem to his colleagues and outlined the difficulties of its proof. The following year, the journal Nature announced that the four color problem had been solved by the English lawyer Alfred Bray Kempe. His proof that the regions of any flat map can be painted with four colors was included in an issue of the American Journal of Mathematics that same year, and for some time the problem was considered solved. Almost 30 years had passed, during which the brightest minds of the time attacked the problem, to arrive at this solution. However, the end of this story was yet to come.
Alfred Bray Kempe was made a Fellow of the Royal Society thanks to his work, and he set about extending the scope of his original article. Other mathematicians also collaborated in this task, presenting alternative proofs. Even Lewis Carroll became interested in the matter and ended up developing a two-person game in which each player designed a map with certain characteristics that the other had to color using four colors. But Kempe's joy was threatened when, in the early 1890s, Percy John Heawood found a serious error in the lawyer's proof.
Heawood wrote an article ('Map-colour theorem') and presented a map of 18 regions that, despite being colorable with only four colors, demonstrated that Kempe's work was far from general. Shortly after, a 'rebellious' map of only 9 regions finished off what remained of Kempe's proof. Again we were where we had been in the 1850s, although Heawood proved that any map can be colored with five colors and that three are not enough, the empirical number of four used by cartographers for centuries still resisted the efforts of the mathematical community.
The Computer-Aided Proof
All this fuss served to make the problem so famous that it was proposed through the London Mathematical Society as 'an important problem to solve.' In 1976, one hundred twenty-four years after Guthrie complicated the lives of five or six generations of mathematicians, two specialists from the University of Illinois (USA) used a Cray computer to color 1900 different types of maps and, after working for 1200 hours, it was verified that it was impossible to draw a map that could not be painted with only four colors. But, despite their effort, Kenneth Appel and Wolfgang Haken had not achieved a proof in the mathematical sense; they only used the 'brute force' of the Cray to check a large number of maps.
The Final Proof
We could never be sure of the non-existence of a twisted design that escaped the four color theorem. This dilemma continued to torment mathematicians for two more decades, until finally -in 1996- Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas, all from the School of Mathematics at the Georgia Institute of Technology (USA) found a proof that, at least until today, is accepted by all their colleagues. It took 150 years for the four color theorem, a problem that all cartographers had solved in practice, to be mathematically proven.
For more information, see the theorem on Wikipedia.
https://old.neoteo.com/por-que-todos-los-mapas-del-mundo-que-conoces-estan-errados/
