Some "Eurekas" of Mathematics - Part Four
First published: Saturday May 29th, 2021
Report this blog
Origin of the Four Color Theorem
The Four Color Theorem's (FCT) origins come from the 19th century when Francis Guthrie discovered that it only took four colors to color in a map of the counties of England. At first, you may think that this wouldn't have much to do with mathematics, but it wasn't until the last 20th century that this formally proved to be true by mathematicians (with the help of a computer). Guthrie and his brother brought this to their professor, the famous Augustus De Morgan, who was unable to determine if Guthrie's hypothesis was in fact true.
FCT in Graph Theory
It would help to first clarify what exactly is graph theory. It is basically what it sounds like. It is a branch of mathematics which studies graphs, which will generally look like the following.
I personally don't know much about graph theory, but using the proper technical terms of graph theory, the FCT says
"for a loopless planar graph G, the chromatic number of its dual graph is χ(G*) ≤ 4."
Or in simple layman's terms, "given any separation of a plane into contiguous regions, the regions can be colored using at most four colors so that no two adjacent regions have the same color."
The Proof
Proving the FCT here would not be possible. Perhaps that main reason that the FCT wasn't proved until 1976 is because it's impossible to do without the aid of a computer. That is to say, the necessary calculations needed to prove that this is true can't be done easily. So instead, a computer was used to consider all possible map configurations and test to see if only four colors can work. Maybe if a mathematician worked nonstop for a year straight, he/she would be able to do all of this by brute force, but why do that when a computer can do those calculations for you in much less time?
If you're interested, here's an outline of their proof I found on wikipedia:
If the four-color conjecture were false, there would be at least one map with the smallest possible number of regions that requires five colors. The proof showed that such a minimal counterexample cannot exist, through the use of two technical concepts:
1. An unavoidable set is a set of configurations such that every map that satisfies some necessary conditions for being a minimal non-4-colorable triangulation (such as having minimum degree 5) must have at least one configuration from this set.
2. A reducible configuration is an arrangement of countries that cannot occur in a minimal counterexample. If a map contains a reducible configuration, the map can be reduced to a smaller map. This smaller map has the condition that if it can be colored with four colors, this also applies to the original map. This implies that if the original map cannot be colored with four colors the smaller map cannot either and so the original map is not minimal.
Applications
Arguably the best part of graph theory is its applications across so many fields. The most famous application for the FCT is of course cartography (that is how it first arose after all). That's why I thought this would be a good topic for the fourth installment of this series, since Jetpunk is so into geography and maps. So let's conclude this exploration of the Four Color Theorem by taking a look at a variety of different maps that surprisingly satisfy the Four Color Theorem.
The colors of this theorem can change? Like, Brazil can be blue, and not green?
I can change the colors at World Map, but without break FCT?