Although I had heard about this theorem many a times, I had never cared to find out what it meant; mainly due to usual complicatedness associated with most mathematical theorems. But the simplicity of this problem attracted me. Here, I’m not trying to add anything new, but will simply attempt to give a simple insight in layman’s terms what the theorem means or at least how I understand it. As Wolfram MathWorld puts it,
The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color.
When I read this, it appeared to defy logic and I began to verify if it was actually true?!! (Although I knew it could never be wrong!). A simple 2D map to start with can be the Google Chrome logo. Its a simple map with 4 regions with every region connecting 3 other regions. So, it requires 4 distinct colors. Now, the possibility of a map to necessarily have 5 colors requires at least 5 regions with every region connected to 4 other regions. This is quite simple to comprehend. Next, I tried to come with a map which meets the above requirement. Now the problem arose. I started with the Chrome logo as shown in fig(a).
To make it into 5 regions I needed another region which connects to the maximum number of current regions. So, I drew another outer circle. Now, all of the previous regions except the center green one is connected to 4 regions. Thus the outer and inner regions are disconnected and hence can be painted with same color as in fig(b) yielding 4 distinct colors.
Now to make these 2 regions connected, I’ve to protrude the inner region to connect to the outer one. This can be done in 2 ways.
Case 1: If this protrusion occurs on the boundary of 2 regions say red and yellow, as in fig(c), then, the red and yellow regions get disconnected and hence can be painted with same color as in fig(d).
Case 2: If the protrusion is in the middle of other region, say yellow one as in fig(e), then the upper yellow region gets disconnected with blue and hence can be painted blue while the lower one can be painted red, as in fig(f) again yielding 4 colors.
This led me to make a daring conclusion, which is nothing but another way of stating the theorem itself.
Its impossible to draw a 2-dimensional map with 5 regions such that each region connects to every other region.
Although this is quite a simple example, the approach for a map with more than 5 regions is much more difficult to deal with.