Six colors for an unimaginable number of circles

Draw a set of circles in different colors on a sheet of paper. The circles do not have to be the same size and they may overlap. There are two conditions. One: No more than two circles may touch at the same point. Two: two circles that do touch each other at the same point must be of different colors. Question: is five colors always enough, regardless of the number of circles?

This question was raised in 1959 by the German Gerhard Ringel, a mathematician (and avid surfer and butterfly collector) who became famous for the so-called graph theory. To be clear: intersecting circles do not have to be colored differently. In a 1984 article, Ringel gave two configurations of circles that require five colors: one contains eight circles, the other (shown here) nine. It is not possible to color the circles with only four colors under the specified conditions. For any configuration consisting of a maximum of seven circles, at most four colors are sufficient.

The books don’t tell you how much effort Ringel went through to find a configuration that would require six colors, but it is certain that he never found one. Hence his question whether five colors are always sufficient.

That question is now answered by five mathematicians from universities in Canada, Israel, Germany and Poland. No, is the answer. The great thing about their result is that they do not give a single example of a circle configuration requiring six colors, but provide a general proof that there is no limit at all to the number of colors required. So it is possible to draw a series of circles for which even a thousand colors are not enough.

In theory that is, because the number of circles required is large. Very large. Even a drawing that requires six colors is practically impossible to carry out. In an email, Linda Kleist writes: “Already for six colors, the number of circles in our construction is (probably) greater than the number of atoms in the universe.” So it’s no wonder that no one ever trial and error found such a configuration.

How did the quintet proceed if you cannot actually put such a configuration on paper? “Our proof is inductive,” says Kleist. “Our method shows that if you have a configuration A that cannot be colored with four colors, you can construct a new, much larger configuration B that cannot be colored with five colors. You can then use B to create a configuration C, following the same principle, for which six colors are not enough.” You can go on like this endlessly. Again and again you can find a new, larger configuration of circles that require an extra color. Kleist: “In this proof of induction we use an old theorem of the Hungarian mathematician Tibor Gallai, which we had to adapt to make it suitable for our purpose.”

no computer

Ringel’s circle problem is reminiscent of the famous four-color problem, which involves coloring a map in such a way that no two adjacent countries have the same color. If the additional requirement that circles must not overlap is added to Ringel’s problem, it amounts exactly to the four-color problem. In 1976 it was proved that four colors are always sufficient. It is therefore surprising that without the overlap restriction the number of colors required is not limited.

For the proof of the four-color problem, the help of a computer was indispensable. But the proof of the five mathematicians is very different. They give a purely logical reasoning, without the need to calculate thousands of cases. The computer was only needed to communicate with each other. The five have been working on the issue since they met in September this year, during an online workshop. Kleist: „We had long zoom meetings and we kept in touch via the screen even after the workshop. Most of us have never met the others in person.”

What is the result good for? “You can ask this question about many mathematical problems that have been open for years,” says Kleist. “Sometimes the methods of proof used are more important than the proof itself. We hope that this is also the case with our evidence. Time will tell.”