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!