The problem of four colors: How many are enough?

What is the minimum number of colors needed to color any map with the only restriction that two neighboring regions do not have the same color? The four-color theorem states that for coloring any map without two neighboring regions being illuminated with the same color, four colors are sufficient.

The problem of four colors: How many are enough?
Theorem of the four colors explained. Photo by Philip Veater / Unsplash

Some problems would have no relation to mathematics, for example, coloring a map is something that one would think is only done in geography class. However, mathematics goes beyond what we are used to seeing. Coloring maps is something that has been done for centuries, a well-colored map is easier to interpret.  In the 19th century, a problem was proposed that over the years became a powerful theorem in mathematics. The problem states the following: What is the minimum number of colors needed to color any map with the only restriction that two neighboring regions do not have the same color?

The answer would seem to depend on the type of map, for example, a chessboard can be colored with only two colors. However, this is a very particular case of map, mathematicians are interested in finding relationships that apply to all cases and therefore the question is posed for any map. It is important, to avoid any confusion, to define what it means for two regions to be neighbors. By this, we mean that the regions do not have any piece of the border in common, except, if it is the case, a point.

As soon as the problem was posed, mathematicians began to look for an answer. Very soon they realized that three colors were not enough, that is, that there were maps that when colored with three colors, no matter how they were illuminated, always had two neighboring regions of the same color. Later, they realized that five colors were more than enough, if any map was carefully colored, five colors were enough and even enough so that two neighboring regions were not of the same color.

The mathematicians were not satisfied with these results, what they were looking for was the smallest number of colors with which any map could be colored. So they thought that if three colors were not enough and five colors were too many, the ideal candidate should be four. They then postulated what is known today as the four-color theorem:

To color any map without two neighboring regions being illuminated with the same color, four colors are sufficient.

It was not until 1976 that two mathematicians from the University of Illinois in the United States, Wolfgang Haken, and Kenneth Appel, found proof that since then has been very controversial because of a new fact in mathematics and that also seems to be very simple: they used a computer. The proof consisted of the computer analyzing and verifying that the theorem was true for millions of maps. It should be clarified that these millions of maps represented, in some way, all the possible types of maps that can exist and that is why many mathematicians considered the proof to be valid.