The 4 Color Theorem

My 8 year old son Julien, who has the ability to quickly "see" math, came to me and out of the blue started talking about some math issue. Unlike Julien, I'm a bit more of an incubator. When it comes to math, I need more time and a bit of "Zen staring" as my late and dear friend Alexey Pilipenko used to call it. Julien started rambling about something regarding even and odd numbers meeting. Even meant you needed 2 colors, odd meant you needed 3. 4 was always sufficient. And what you never, ever needed was 5. I had no idea what he was talking about. Then he said something like, "you know that map thing...that map problem", and I vaguely remembered something about a theorem on how many colors it takes to clearly distinguish regions on a map.

I sat down with Julien so he could show me what he meant. Per his instructions I drew a simple map. Julien pointed and said all you needed were 2 colors if "even numbers met at the point". If odd numbers met you needed 3. If there was a combination of points with odd and even numbers on the map, you needed a forth color. But you never needed 5, he emphasized again. I quickly tried out a map that seemed like it would need 5, placing numbers in the regions instead of colors. But before I could clear the Zen veil, Julien rapidly rearranged the numbers to prove 4 colors were sufficient.

Since I was vaguely familiar with the 4 color theorem, I didn't question the stated premise that 4 colors always sufficed for a map on a simple plane. But it suddenly intrigued me immensely. And what was it Julien was really pointing out about odd and even numbers? By this time Julien was already off to something else. Unperturbed by the problem, Julien was reading a book on the kitchen floor. His poor father, on the other hand, sat mesmerized at the kitchen table, drawing maps, Zen gazing at number coded regions, leaning his forehead against his knuckles.

This much was clear. Julien was absolutely right. If you chose a point where an even number of lines met on the map, call it an even vertex, you needed only 2 colors to distinguish the regions surrounding the vertex. But for an odd vertex, that is where an odd number of lines met, you needed at least 3 colors. Why? Because if you circled around the regions surrounding an odd vertex and alternated colors, by the time you reach the region neighbouring the region you started at, you would end up with the same color as you started with! It can easily be shown using a numeric sequence:

1, 2, 1, 2, 1

Any sequence with an odd number of alternating elements would end with the same element it started with. Since the regions around a vertex form a circle, blue ends up against blue, making it hard for us on a 2 colored map to tell a blue Sweden from blue Norway if Finland is red. It occurred to me that we can talk about binary pairs. Why? Because any line on a simple plane divides the plane into a binary pair. There is a region left of the line and a region right of the line, i.e. a binary pair of surfaces. Expressed numerically:

0,1

With an odd vertex, there will always be an incomplete pair:

0:1 , 0:1 , 0

We need to remember that the sequence is circular. And, importantly, each element should be able to form a binary pair with both of its neighbours. If we shift over the elements in the above sequence, we get:

0 , 1:0, 1:0

It doesn't matter how we shift it, left or right. There is simply one zero too many for all elements to form pairs. If we bond the start element with the end element, we get the flawed pairing:

0:0 , 1:0 , 1

So in an sequence with odd elements, we need a third type of element:

0, 1, 0, 1, 2

Now we can form a perfect pair (a pair were the two elements are of a different type) even if we pair the start element with the end element:

2:0 , 1:0 , 1...2

If we shift again in the same direction:

1:2 , 0:1 , 0...1

Now, what about that 4Th color? So far we have just had one vertex and rays (or lines) emanating out to the very edge of the plane (our map). If we cut rays somewhere before the reach the edge of the plane, and then attach each cut end to the ends of the two closest rays, we essentially get a triangulated polygon. If we want to clearly distinguish all the triangulated surfaces of a polygon that were formed around an odd vertex from the rest of the plane, the plane will have to have another color than any of the colors in the inner sequence (since the plane borders on all of the surfaces). In numeric terms, we can think of it as adding another sequence layer:

3

0, 1, 0, 1, 2

The element in the upper sequence should be able to bond and form perfect pairs with any neighbour in the lower sequence. In the above example, 3 borders on all elements in the lower (or innermost in spatial terms) sequence. It would be easier to picture this if we used colored squares instead of numbers. Above sequence works because the 3 can bond well with any of the 0, 1 or 2's below:

3:0 , 3:1 , 3:0 , 3:1 , 3:2

What if we divide the plane surrounding the triangulated polygon into 2 surfaces:

3, 2

0, 1, 0, 1, 2

Now we need to establish which elements of the upper sequence have to be able to form pairs with which elements in the lower sequence (or who is a neighbour of whom). Remember that the upper sequence forms a "circle" around the "circle" of the inner sequence. If two elements are neighbours "diagonally" it doesn't matter that they are of the same type. If the 3 in above sequence is only above the first zero in the lower sequence, then we get the following required pairs:

3:0

2:1 , 2:0 , 2:1 , 2:2

And, we have a problem Huston. There is a 2:2, which is an imperfect pair! How can we solve this? It's easy. All we need to do is replace the last 2 in the lower sequence with a 3, which will not be a problem since there are no 3's yet in the lower sequence. All elements in the circular lower sequence will therefore still be able to form perfect pairs with their two neighbors. The lower sequence then becomes:

0, 1, 0, 1, 3

The 3 in the upper sequence is still only above the first zero, forming the perfect pair 3:0. So lets check the The 2 in the upper sequence against all its neighbors in the lower sequence:

2:1 , 2:0 , 2:1 , 2:3

Which are all what I have repeatedly referred to as perfect pairs. It doesn't matter where we put the borders between the lower and upper sequence. Let's say we place it half way between the second and third element in the lower sequence ( the first 1, the second zero ). The upper 3 forms pairs:

3:0 , 3:1 , 3:0

The 2 of the upper most sequence now has to form fewer pairs:

2:0 , 2:1 , 2:3

But what if we move the border of the upper 3 all the way to the 3 of lower sequence (so both the 2 and the 3 in the uppermost sequence border the last element of the lower sequence)?

2:3

3:0 , 3:1, 3:0 , 3:3

Suddenly we have an imperfect pair again (a 3:3). It's self-evident that each element of the uppermost sequence will border a maximum of three types in the lower sequence (since we need only three types to distinguish the surfaces around an odd central vertex). It's also evident that, in the beginning, only the last element in the lower sequence needs to of a unique third type (since even sequences can just alternate between two types).

Only a maximum of two elements in the higher sequence will have to have the capacity to border on three types in the lower sequence (since only the last element in an odd lower sequence has to to be different). As soon as you place three elements into the higher sequence, at least one will have to border on only two elements in the lower sequence.

In the case where only one element in the higher borders three in the lower, only that higher element must, by necessity, be a forth type. The type of the other elements in the higher sequence are thereafter dictated by the type of the element that borders three types in the lower. If the higher sequence has an even number of elements, all pairing will be perfect. If, on the other hand, there are an odd number of elements, the last element must be different from the two primary alternating elements in the lower and the forth type, which is where we seem to run into a problem.

However, in any sequence you can replace an element between two types with a third type without destroying the elements ability to form perfect pairs with their neighbours:

0, 1, 0, 1, 2 => 0, 3, 0, 1, 2 => 0, 3, 2, 1, 2

Interestingly, assuming you use at most 4 types, Any time this is done, at least one alternation remains. In the above example we switched from a 0 / 0 alternation in the two first to a 2 / 2 alternation in the last sequence. But that not so important for us.

The important thing is that if there is an odd number of elements in the higher sequence (assuming only one element in the higher sequence borders three types in the lower), we can just switch the offending last element of a forth type with the second type of the primary alternating elements in the lower (i.e the 1 in our case). The offending element becomes a 1 and all the 1's bordering that element in the lower sequence become a 3.

Now interestingly, the only way to get two elements in the higher to border three types of elements in the lower, is to make a small element bordering only the last element in the lower (which is of a third type). 

Wow, fascinating. I think this will require another post....