Some "Eurekas" of Mathematics - Part Four

+12

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.

An example of a simple graph

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 world map
A map of the United States
Municipalities of Slovenia
Oblasts of Russia
+1
Level 43
May 29, 2021
Is there a Brazilian Color Theorem?
+1
Level 74
May 29, 2021
As in a map of the states of Brazil that uses just four colors?
+1
Level 43
May 29, 2021
Yeah.
+1
Level 43
May 29, 2021
And I still don’t understand lol

The colors of this theorem can change? Like, Brazil can be blue, and not green?

+1
Level 74
May 29, 2021
In order to color-in a map, you only have to use four different colors to assure that no two regions with the same color share a border.
+1
Level 43
May 29, 2021
Now is comprehensible lol

I can change the colors at World Map, but without break FCT?

+1
Level 74
May 29, 2021
Yes
+1
Level 39
May 29, 2021
Lol Philippines is divided
+1
Level 51
May 29, 2021
...and Czechoslovakia and Turkaijan are countries...
+2
Level 74
May 29, 2021
Turkaijan?
+1
Level 51
May 29, 2021
Turkey and Azerbaijan
+1
Level 74
May 29, 2021
The countries aren’t combined. They simply are using the same color. You didn’t notice there are only four colors being used? Did you read the blog?
+1
Level 51
May 29, 2021
But I thought that there weren't supposed to be two countries bordering each other, with the same color? Or was I wrong?
+1
Level 74
May 29, 2021
Ahh, okay, I see your point. Looks like the person that made the map ignored that part of Azerbaijan that touched Turkey. Whoever made it obviously isn't a geography nerd since there are a few things (like that, the fact that Jordan technically borders the Red Sea, etc.) which aren't accurate.
+2
Level 39
May 30, 2021
And maybe the person that made this map thought Czechoslovakia still exists...
+1
Level 43
May 30, 2021
The same person thought South Sudan isn’t a country.
+1
Level 39
May 30, 2021
I guess this map made before 2011.
+1
Level 51
May 30, 2021
No.... before 1994. Because Eritrea is part of Ethiopia.
+1
Level 39
May 30, 2021
OH GOD THIS MAP IS VERY WRONG
+1
Level 39
May 30, 2021
Wow now I noticed. Yemen-Saudi Arabia border...
+1
Level 51
May 30, 2021
...and Moldova and Japan.
+1
Level 39
May 30, 2021
...and Niger, Nigeria, Chad, Cameroon border...
+1
Level 39
Jun 17, 2021
...and I don’t want to mention about Kosovo...
+1
Level 66
May 29, 2021
I also realized that all the cyan countries are landlocked (probably to distinguish them from the unnaturally neon ocean)
+1
Level 74
May 29, 2021
Yes, they are demonstrating in the image how even if you count the oceans/seas as a region on the map, you still only need 4 colors
+1
Level 54
May 30, 2021
Yeah, this quiz is impressive but it should use that sample so countries couldn't get merged
+1
Level 65
May 30, 2021
There are large borders