The 4-Color Theorem
The above picture is a map of the world as all of us know. But if you look at it a bit closely, you will find that the entire map has been colored using only 4 colors. That’s right. Only 4 colors to color all the 195 countries in the world!! Another additional fact is that: No 2 adjacent countries (i.e countries that share a border) have the same color
This is precisely what is known as the 4-color theorem.
Any map can be coloured using only 4 colours such that neighbouring countries do not have the same colour
The definition of neighbouring countries is that, they do not share a border
Simple Exercise
Consider this simple exercise you can try out for your own. The below figure has 5 regions. How many colors do you require to color it so that no 2 neighbouring regions have the same colour?
The answer is 3. How? Let us start from the innermost circle. Let me color it red. Now. moving to the top right quadrant, I can’t color it red since it is sharing a border with the inner one. Let me color it blue
Now. coming to the bottom right quadrant. It is sharing a border with both red & blue colored regions. Hence, I have to give it a new color. Let me color it green
Coming to the bottom left quadrant. You would think we have to give it a new color right? Not exactly. As you see, it shares a border with the green and red regions. But wait. It has nothing in common with the region we colored blue? So, yes. We can color it blue. Applying the same logic to the remaining region, we can color it green.
You can see the sequence of steps in the below figure
All it took was 3 colors to color this 5-region figure. Next, you can try out the below 2 figures and see how many colors you require to color them. If you go beyond 4 colors, do drop me a message
The History
Around 1852/1853, an over zealous man was trying to color the counties of Britain who thought it could be done using 4 colours only. He said this to his brother, who was a maths student, who in turn, passed this on to his lecturer, a man called Augustus DeMorgan. It was DeMorgan who spread this around the mathematical community
Attempts to Prove
Proving the 4-color theorem proved to be a difficult task. You either had to prove it for 4 or show a contradiction i.e show a map with 5 colors satisfying the conditions. By 1976, mathematicians were able to prove till 5 colors, but were unable to bring it down to 4
In 1976, Kenneth Appel and Wolfgang Haken provided a computer assisted proof, which involved iterating through 1936 configurations of maps by a computer which took over 1000 hours.
A shorter and much simpler independent proof was provided by Robertson et al around 1996, which was verified by Gonthier of Microsoft Research in Cambridge in Dec 2004. He claimed to have verified Robertson’s proof by formulating it in the equational logic program Coq and validating each and every step
A few other examples of maps colored using 4 colors:
Thanks for reading!!!
References
Originally published at http://infinitesimallysmallcom.wordpress.com on June 6, 2021.
