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.
RESOURCES
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.)
Other
Here is some interesting recent news about the problem:
Here are some great sources about graph theory in general:
http://dimacs.rutgers.edu/~hochberg/undopen/graphtheory/graphtheory.html (this one is only unsolved problems!)
CONCLUSION
Wow, this article ended up being the longest I've ever written! I hope you've learned something interesting about graph theory and that you've begun to appreciate something of the beauty of the clever arguments in math as a whole.
There are so many open questions in graph theory today (it's a relatively new field), and I'd love to talk about it even more as it's so fascinating to me. If you're interested, google the Graceful Tree Conjecture, the Bridges of Königsberg, the Utility Problem, the Stable Matching Problem, Dijkstra's Algorithm, and so on!
I've found that problems in graph theory often don't rely on one another overly much, as they involve lots of different things you can do with a graph, like coloring it or traveling along the edges, but they still break down to the same concepts: edges and vertices. It's such a wide and exciting field.
Feel free to leave any questions, comments, or feedback in the comment section, in the forum or even in the contact form through GLeaM's homepage. Make sure to subscribe as a member or a subscriber (or both!) to receive emails from GLeaM and learn about new articles as well as other updates: from updates about what else GLeaM is accomplishing to exciting math-related opportunities in my hometown, Atlanta, and across the world!
Below is the proof of the lemma we used in both the proofs of the Six Color Theorem and the Five Color Theorem. It's the last piece to fully understanding the problem.
APPENDIX
Proof of the Lemma: Every planar graph G must contain a vertex of degree ≤ 5.
Let's say that the vertices of our graph are v1, v2, v3, v4... and the total number of edges is E and the total number of vertices is V. Let's also assume our graph is connected for the time being. (Here, connected means that there is a set of edges connecting every vertex to every other vertex—which is mostly always true for maps unless there are islands.)
We'll approach the lemma by contradiction. If for some reason our lemma wasn't true, every vertex would have degree at least 6:
Then the total degree of the vertices (which is equal to 2E, as every edge is counted twice in the total degree of the vertices) can be expressed as follows:
2E = deg(v1) + deg(v2) + deg(v3) + deg(v4) + ... ≥ 6V, so E ≥ 3V.
However, a statement we know is always true in graph theory is E ≤ 3V-6, as long as we have at least 3 vertices.
This one comes from a formula called Euler's Formula: F = E - V + 2 that is true for connected planar graphs. This is the only bit I won't explain but you can understand its proof, so go here for more!
Here, F is the number of faces of the graph (the regions between the vertices and edges), and you also must include one face for the exterior outside the graph.
For example, the graph below has 4 faces, 3 shapes clearly defined within the graph and the outside region counts as a face as well:
Together, with the 8 edges and the 6 vertices, this graph does indeed give F = E-V+2 → 4 = 8-6+2
Now, we'll work on getting the inequality above out of Euler's Formula.
Because every edge in a graph is attached to two faces (one on each side of it) or one face twice (if the face flows on either side of the edge), the total sum of the face boundaries (the number of sides bounding each face, or the outside border for the outside region) for a connected graph is equal to 2E.
Further, since every face has at least three edges bordering it (the easiest way to think about this is that a triangle is the smallest shape as long as we have at least 3 vertices (our initial assumption), but it's a little more nuanced than that, so think about it for a bit and see if you can convince yourself of this fact—note that if an edge is merely a line, it counts as part of the outside face and it is counted TWICE), we know the total sum of the face boundaries is at least 3F.
Then 3F ≤ 2E.
From here, we plug in Euler's Formula:
3(E-V+2) ≤ 2E
3E - 3V + 6 ≤ 2E
E ≤ 3V - 6.
Since E is always less than or equal to 3V - 6 for V≥ 3, E cannot be greater than or equal to 3V for V≥ 3, so our initial assumption that our graph had NO vertex with degree less than or equal to 5 must be FALSE. Therefore, there MUST be AT LEAST ONE vertex with degree less than or equal to 5.
This is the essence of a proof by contradiction, showing that if a statement were not true, something fundamentally contradicting (like the statement E ≤ 3V - 6 for planar graphs) will occur, so the original statement must be true.
Note that if the number of vertices is not greater than or equal to 3 (i.e. 1 or 2), each vertex can't have a degree greater than 5 anyway, so our statement holds true for that case as well.
Therefore, our lemma is true for planar connected graphs.
This can be expanded to any planar graph (including ones that aren't connected) because you're essentially lowering degree and number of edges (and keeping number of vertices the same) if you take a connected graph and make it not connected, which creates no scenario for E ≤ 3V-6 to be overturned or for the degrees of individual vertices to increase. (Then, the total sum of the face boundaries is less than 2E, so 3F is still less than or equal to 2E.) Therefore, we can say the lemma is true for all planar graphs.
There's an interesting way to go about this with matrices as well—leave a comment if you want to see that method.
You can check out this article for another interesting way to prove our lemma by contradiction without using the E ≤ 3V-6 inequality: https://nrich.maths.org/6291
This lemma is also called the Only Five Neighbors Conjecture if you want to search it up further!
I didn't include every single detail of the proof, but that should be more than enough to get you started, so see if you can convince yourself fully that the lemma is true.
That's it! Have a great week everybody!
Cover Image Courtesy of Catchtest.Pixnet.Net
UPDATE: As of December 2020, I have posted a three-minute video explanation of the concepts discussed in this two-part series. Visit it here: https://www.youtube.com/watch?v=vNb6sLzbM0A