Exploring The Four Color Theorem: Part 2
Updated: Dec 30, 2020
Welcome back to my series on graph theory! Today, we're continuing our discussion of the Four-Color Theorem. Go here for the first part of the article—you'll need to understand the concepts from the first article to understand this one!
In addition to all the theorems we've already proven, the first article includes all the definitions and explanations you'll need to approach this one. I'll be recapping some concepts as we go along, however, so if you just need a refresher, you can stay here!
This is a long article in part because of the recap, but there's also some really exciting, fun math here. A lot of it can be difficult, but stick with it! You got this!
As a brief recap, the question we're trying to answer is this one: Given any map (think of a map of a continent or a map of the US), we wish to color the map so that any two regions sharing a border are two different colors. What is the minimum number of colors we can use to guarantee we are always able to do this on any map?
Last week, we realized that you can color the US map in four colors like in the image below, and like many mathematicians all the way from the 1850s when the problem was stated to 1976 when it was solved, we believed that the answer to the problem is four colors for any map, regardless of how it is drawn, but we could not yet prove it.
The term we used to describe a map that can be colored in n colors is n-colorable. We realized that the US map is 6-colorable, 5-colorable, and finally, 4-colorable. Any map that is 4-colorable is 5-colorable, but we don't yet know if any map that is 5-colorable is also 4-colorable.
We decided that we were going to work our way down to proving that any map is 4-colorable (a statement known as the Four Color Theorem) by way of first proving it can be done in six colors (the Six Color Theorem) and that it can be done in five (The Five Color Theorem). Having proven the Six Color Theorem in the last article, the task at hand is now to prove the Five Color Theorem.
We framed the problem in terms of graph theory, where each region/state/country is represented by a vertex and every two regions/states/countries that share a border are connected by an edge. The task then becomes to show every planar graph (a graph where none of the edges cross each other—which is also a property of graphs formed by maps) is 4-colorable such that every edge connects two vertices of different colors.
Ok, without further ado, let's move to the Five-Color Theorem!
The Five-Color Theorem
The proof is an extension of the proof of the Six Color Theorem that every planar graph is 6-colorable (again, in last week's article!) so let me remind you of a couple of things.
The term degree defines how many edges come out of a given vertex, and by a lemma (that I'll prove at the end of this article), we know that every planar graph must contain at least one vertex of degree 5 or less.
To prove the Six-Color Theorem, we used a strategy called induction to work our way through the possible scenarios. Knowing that the Six Color Theorem is true for 6 or fewer vertices (there are more colors than vertices!), we showed that if the Six-Color Theorem is true for k vertices, it's also true for k+1 vertices, creating a domino effect that proves the statement for any number of vertices (The fact that 6 vertices works would imply that 7 vertices works, 7 would imply 8, 8 would imply 9, and so on). To do that, we showed that any graph of k+1 vertices is 6-colorable if every graph of k vertices is 6-colorable. We isolate the vertex on the graph of k+1 vertices that has degree 5 or less:
Here, the central vertex has 5 or fewer connections (edges) and each of the vertices it's connected to can have any number of additional edges and can even connect to each other in various ways. We simply isolate this specific vertex to look closer.
Then, all we need is the fact that the graph without this vertex (the one below) is assumed to be 6-colorable by our induction argument because it has k vertices, and therefore, the graph with this vertex is also 6-colorable because the last vertex can be colored a sixth color that is not represented. Therefore, our induction argument is complete, and we know that the Six Color Theorem is true.
Having reviewed that, it's now time to extend this to the Five Color Theorem. We're now proving that every planar graph is 5-colorable. Let's begin our induction argument. (Remember the terms base case, induction hypothesis, and induction step from last week's article?)
The base case of our induction is true for similar reasons to the Six Color Theorem. We know the Five Color Theorem is true for 5 or fewer vertices because there would then be more colors than vertices, so no edge would need to have 2 vertices the same color. Note that for both theorems, we only really need to prove the theorem is true for one base case, the smallest one—1 vertex—but in this proof, we get several cases for free.
Again, for our induction hypothesis, we assume that the Five Color Theorem is true for k vertices. For our induction step, the goal is to show that given the induction hypothesis that any graph of k vertices is 5-colorable, it must also be true for k+1 vertices: any graph of k+1 vertices is 5-colorable. Then, the dominos of our induction argument will fall and the statement will be shown to be true for any number of vertices.
We'll again look at the vertex on our graph of k+1 vertices with degree 5 or less. Our goal is to show that you only really need 4 colors to color the remaining vertices around that vertex, and then, the final vertex can be colored a fifth color, and therefore, the overall graph is 5-colorable.
Note that if our vertex has degree 4 or less, we're already done: We can simply color our vertex the fifth color that is not represented in the other 4 vertices.
With that case out of the way, let's assume the vertex has a degree of exactly 5, and see if we can prove we can color the vertices around it (the colored ones below) with only 4 colors. Let's start with a valid coloring that has 5 colors surrounding our central vertex, and see if we can eliminate one color by changing the coloring in some way and still creating a valid coloring.
Let's see what happens if we decide to make that red vertex green.
If any vertices connected to our originally red, newly green vertex are already green, we have to change them. Let's make them red.
If any vertices connected to the newly red vertices are already red, we have to change them. Let's make them green.
If any vertices connected to the newly green vertices are already green, we have to change them. Let's make them red.
You see where this is heading? We continue this process until it either terminates or we run into a problem. If the process terminates and every vertex involved is successfully changed to the other color without any problems, we're done. We now have a graph that is successfully colored in 5-colors that looks like this:
And we can make the central vertex red. Success!
But what if we do run into a problem? Let's consider what a problem means. There would be a problem if our process told a vertex to be both green and red, like if there was a cycle (here, a cycle is any series of edges that connect back to themselves, essentially forming a closed polygon) that somehow connected back on itself like this:
The arrows here show in which direction our process moved to color the vertices: from a vertex that was originally green to one that was originally red to one that was originally green to one that was originally red: creating red, green, red, green.
Here, we have a green vertex that is connected to both a green and red vertex, so we don't know what color it will be. But here's the deal: this situation could never happen! We're dealing with a coloring we know was already valid at the start (by our induction argument), so we know the graph had no edges with two red vertices or edges with two green vertices at the start. Our "problem" graph would have looked like this at the start:
This isn't a valid coloring because it has a red-red edge, so this contradiction is not possible—the starting conditions that result in this kind of issue can't exist in our scenario. I'll give you a second to convince yourself that this reasoning can extend to throw down any supposed contradiction where we don't know what color to assign a vertex.
Our process does not run into any problems with assigning our vertices colors as no vertex we're dealing with can be connected to both green and red, because then it would not be green or red to begin with. When we complete our process, we're simply switching the colors in an already valid system, so it does indeed remain valid.
Our process deals with every single red and green vertex that is in any way connected to the changing of our red vertex to green, as it checks all the connections outward from each vertex for the opposite color, and we also know that we won't run into any problems with blue, orange or purple, as they'll still be different colors from the red and green.
Seeing that, we now know the process does indeed run into no contradictions in assigning the vertices red and green and each vertex is assigned a color correctly. Thus, we know this process can iterate all the way through in the space surrounding our central vertex and its five connections. Assuming this doesn't change any other of our five vertices, we've successfully changed our red vertex to green which is exactly what we wanted!
There is only one situation we need to account for. What if our process does change our original five vertices?
First, let's think about if we can somehow change our blue, orange, or purple vertices. You might think there is a possibility that they can become red or green, like the following connections to our originally orange vertex:
In this case, the connections eliminate one color, and we can color our central vertex that color.
But, ALWAYS carefully check your proofs! While this seems like a good way to justify this case, note that all it takes here is realizing that the blue, orange, and purple vertices can NEVER become green or red, because our chain of turning vertices to red and green only involves alternating vertices that are ALREADY red or green. This is all we need for this case: all we do is note that we can never mess with our original configuration by changing a vertex that's not red or green. It's always important to look for pitfalls; even justification that seems to take you to where you want it to can have holes in it.
Here's a scenario where a problem could emerge: what if there's a series of connections from our original red vertex to the green one?
Here, we either have:
This last scenario, where we have a cycle that contains an odd number of vertices (including the central vertex) connecting the green and red vertex, is the ONLY scenario where we run into a real problem. Here, our colors switch places and we still have all five colors represented around the central vertex, which does not give us a possibility to give the central vertex a fifth color.
But, thankfully, there's a workaround! There does exist a process where we can still eliminate a color if this last scenario occurs.
Here's where the secret lies: we can do the same thing to blue and orange!
Given the graph we already have where we have a cycle between the green and red vertex, let's say we want to change the orange vertex to blue. We're going to try to complete the same process: changing the orange vertex to blue, and all the blue vertices connected to that vertex to orange, and so on.
Remember what we just proved: The only scenario where this process doesn't work is if we have a cycle (with an odd number of vertices) that connects the orange vertex to the blue vertex. But guess what? There can't be a cycle!
We're trying to prove that every planar graph is 5-colorable, and remember what the definition of planar is? A planar graph is one where the edges don't cross over each other at all!
If we were to have two cycles, one between green and red and one between blue and orange, there would have to be some crossing of the edges as the two cycles would have to go over each other to reach their corresponding vertices. Therefore, the graph would not be planar.
Therefore, if there is a red-green cycle, there cannot be a blue-orange one, and we can indeed change the orange vertex so that it is blue.
Therefore, even in the initial scenario where our scheme didn't work, we can create a scheme where we will be able to eliminate one color and allow our vertex to be the fifth.
The important thing here is we chose the red and green vertices because they weren't adjacent to one another in terms of the order of the vertices around the central vertex, and therefore a potential blue-orange cycle would have to intersect a red-green one. This is what makes our scheme work.
Here is a brief summary of our process that allows us to eliminate at least one of 5 colors surrounding a central vertex (with degree 5 or less) of a graph with k+1 vertices given a valid coloring in 5 colors for the remaining k vertices in the graph.
If the central vertex has degree 4 or less, simply color it a fifth non-represented color. You're done.
If not, choose one colored vertex of the 5 vertices to correspond to red, and choose a colored vertex non-adjacent to it in terms of the order of vertices around the central vertex to correspond to green.
Change the red vertex to green and change all green vertices that connect to the newly green/originally red vertex to red and all red vertices that connect to the newly red vertices green and so on. If the process ends and does not affect the central vertex and its 5 connections, you're done. If the process does affect the 5 connections of the central vertex but does not change the green vertex that is connected to the central vertex to red, you're done. Color the central vertex a fifth non-represented color.
If not, choose the vertex between the red and green one to correspond to blue and choose one of the remaining two to correspond to orange.
Change the orange vertex to blue and change all blue vertices that connect to the newly blue/originally orange vertex to orange and all orange vertices that connect to the newly orange vertices blue and so on. This won't create an invalid cycle, so you're done. Color the central vertex a fifth non-represented color.
This is a scheme that seems rather arbitrary, but when you think about it, it can be generalized to other scenarios (and we can, of course, choose different colors as long as the order of our colors is preserved), and it's a rather clever, witty bit of math that completes the induction step for us.
That's all there is to the proof. We know that the Five-Color Theorem is true for the small cases of 5 or less vertices, so the base case is complete. Then, since we can always find a vertex of degree 5 or less in a planar graph of k+1 vertices and the remaining graph of k vertices is 5-colorable by our induction hypothesis, the total graph of k+1 colors is 5-colorable because our process keeps our graph of k vertices 5-colorable as we add our fifth vertex.
This shows that any planar graph is 5-colorable, as induction shows that our base case is true and then the induction step shows that each case implies the next. Knowing that the Five Color Theorem is true for 5 vertices shows it's true for 6, and 6 shows it's true for 7 and 7 shows it's true for 8, and so on, all the way up!
This was also in a way a proof by contradiction. We proved that if we were to need more than five colors, the graph would not be planar, which of course, we need it to be!
Whew, that was a lot of math! If I lost you a little bit, feel free to ask me questions in the comments or leave me some feedback about what I can explain a little better. I really hope you gained something from exploring such an elegant proof.
Notice that this is a lot like how mathematicians think. They start with an idea: making the proof of the Six Color Theorem work for five colors by changing one vertex's color, and they build up, coming up with ways to make sure a statement is still true even if they run into problems. The result is the process listed above. All induction takes is a valid scheme, even if it seems arbitrary, and that's exactly what we found here!
Notice also that there were very little numbers here. Except for the degree of certain vertices, we really just relied on logic and reasoning. Math isn't always about numbers, but it is about nailing things down in certainty with mathematical reasoning: something we certainly did here.
The Four-Color Theorem
Unfortunately, as much as I would love to, I can't give you the proof of the Four-Color Theorem here.
The mysterious thing about the Four-Color Theorem is it wasn't proven with the clever logic and reasoning provided here (which also happens to be elegant enough that anyone can understand it with enough thought) but instead with brute force.
Mathematicians Kenneth Appel and Wolfgang Haken proved it with computers in 1976, over a century after the Five-Color Theorem was proven.
They essentially looked at subgraphs, different pieces of graphs that must be in every graph, and brute-forced from there to show all of those subgraphs contained properties that allowed the graphs that contain them to be 4-colorable.
The proof of the Four Color Theorem was something of a controversy because mathematicians had been trying for years to come up with a clever proof along the lines of that of the Six Color Theorem or the Five Color Theorem, and the brute force method almost seemed like hacking the process.
It involved a lot of computer code and results that can't easily be checked by mathematicians in a reasonable amount of time, so though no errors have been found, some mathematicians still don't accept the result.
The problem is so difficult to solve and has become so compelling that it's one of the problems that practically defines the 20th century of math. It's such a short statement to state and to understand but an extremely difficult problem to prove and to fully understand.
The thing about math is it's often more important to know how something is proven than that is true. Entire fields have been discovered on the journey of attempting to solve particular problems (in fact, I'd argue most fields of math have been discovered this way), and many mathematicians still wonder if there's some deeper truth to be found if there were to be an elegant mathematical proof of the Four-Color Theorem.
However, this is finally where we can find the real answer to our question. The minimum number of colors is indeed four. We can't color every map in three colors (just look at Nevada on a US map), and we now know we can always do it in four, thanks to Appel and Hanken.
This article is already long, so I won't give you many more details of Appel and Hanken's work beyond those, but you can check out some of the resources below to learn even more! Their work was still impactful and meaningful even if it was not quite the approach mathematicians were hoping for, so I encourage you to learn more about it.
Five Color Theorem
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/MatthewWahab/5color.html (this is a great explanation of the proof that is a little more concise—it's a great explanation now that you have the background)
Four Color Theorem
https://nrich.maths.org/6291 (This is the best article I've found about the problem, and it also has a great alternate explanation of the lemma below.)
Here is some interesting recent news about the problem:
Here are some great sources about graph theory in general: