Alon Amit on Quora · 2015-08-31

Why is the obvious proof of the four colour map theorem, which says that any planar map can be coloured using only 4 colours, seemingly wrong? If 3 colours are all touching each other, then the 4th colour that touches all 3 must encircle one of them.

I'd like to offer a perspective that may help readers understand more clearly not only why this proof doesn't work, but what is it about this kind of approach that makes it unlikely to succeed.

At a high level, the question proposes a local approach to a global question. We have a map with many bordering countries: there might by ten, fifty or two million of them. The four-color theorem claims that no matter how large or intricate the map is, four colors always suffice to paint the countries such that neighboring countries have different colors.

Notice that this is a claim about the entire map, not about this or that region of it. The entire map can be colored using just four colors.

The argument proposed in the question is a local one. It says "whenever three colors are all touching each other, then... <something good happens>". The problem with such arguments is that they are demonstrably too good to be true. A map (or more generally, a graph) can require very few colors locally while requiring many colors globally, because we can't piece together the easy workarounds suggested by the local methods.

Here's an example. Consider the following map:

It has nine "countries" arranged in a circle, each one bordering just two others. For our discussion we can assume that the inner circle (and the outer region around the countries) aren't countries at all, so we don't need to worry about coloring them. If this bothers you, feel free to add them both as countries; they will require one more color and the discussion doesn't change.

How many colors are required locally? Obviously, just two. If you focus your attention on any country and its neighbors, or even its neighbors' neighbors, and even if you look far and consider the neighbors of these neighbors' neighbors, you only need two colors. Just use an alternating pattern:

two colors are enough here...

and also here...

...and here, too.

So two colors suffice locally, in the vicinity of any single country. And those local colorings seem to cover the entire map, so... surely the map requires just two colors? Of course the answer is No. Those local colorings disagree with each other, and the only way to color the entire map is to use a third color:


The need for this extra color arises due to a global feature of the map. Locally we need just two colors, but globally we need three. If there had been 100 countries in this cycle, two colors would work great. But if there are 101, you need three colors. The deciding factor here is the parity of the number of countries, and the parity is a global attribute: you can't determine if the number of countries is even or odd by looking at a certain horizon around each country. You have to scan all of them.

The four-color theorem asserts that for a planar map, those global mismatches can always be resolved using just four colors. This is very, very far from obvious. Perhaps you can prove that four colors suffice around this country, and four colors also suffice around that country, and also over there... but can you piece together all those local colorings into one global coloring? How do you prove that you can?

In a way, the actual proof of the 4CT does investigate local structures, and it proves that they can be resolved coherently. But the approach is not only more subtle, it actually requires the analysis of thousands of local structures and resolution methods. This is why it is, notoriously, one of the few mathematical proofs that absolutely requires a computer in order to be surveyed and verified.

Originally posted on Quora: https://qr.ae/pFmQvb