Four Colors and a Theorem

(Ed: Some of the original post has been removed. )

There is a small Theorem of Note that says, in short, that four colors are sufficient to color any map such that no two regions that share a border have the same color.

There are of course provisions, for example the regions must be contiguous. The United States would generally be disqualified because of Michigan, but it turns out not to matter in that particular case.

This idea fascinated and puzzled me for a long time after I first heard it. It seems so shockingly general. Given the infinitude of possible border shapes and geometries and arrangments, how could you even begin to approach the problem in a sensible way? Of course, you know how Mathematicians are – always up to something.

The below is a rather long post, encompassing a bit of history of the problem, -a lot- of background and introduction to the problem, a watered down description of old proofs, some analysis of the problem, and current areas of interest with regard to the problem.

It is difficult to discuss the Four Color Theorem and not talk about its relative infamy in the Mathematics community. It’s seen multiple attempted proofs since about 1860, each of which stood a long while before finally falling to closer analysis. Fairly obvious flaws too – someone said once, it was almost like no one was actually reading them. Finally, a complete and seemingly correct proof was accomplished in 1976 through computer assistance – and by assistance, I mean they basically (and I am not doing them justice here) generated every possible map and its four coloring, leading to a 500 page proof that no one has yet had the stomach to check by hand. And people have pretty much left the Theorem alone since. No one likes to talk about it.

And so I shall.

The first step in approaching the problem is to mathematically rigorize what we mean by maps. Elsewise, we will might as well be scribbling shapes with Crayons until the end of time. And the means by which we will rigorize our endeavour is through the use of graphs.

I’ve done some stuff with graphs before, but nothing interesting of late, so a bit of a refresher. Graphs consist of a set of nodes, some of which are connected to each other. You can think of it in terms of a sort of network.

Here is a relatively random graph I grabbed from Mathematica. The black dots are nodes, and the lines show the connections between them. Note that in a general graph, any node can be connected to any other node.

The connection to the problem at hand is that any map of interest can be represented by a graph. Basically, each region of the map to be colored becomes a node, and for countries that share a border, their nodes are connected.

Here is a crudely drawn map, and the representational graph overlaid on it.

Four Coloring the map then becomes choosing colors of nodes such that no two nodes that are connected have the same color. For any graph, the maximum number of colors needed to color the nodes such that no two connected nodes have the same color is known as the Chromatic Number of that graph.

Note though that the sizes of the nodes is irrelevant, they’re just different sizes because I was doing this freehand.

The prompt I left the other day is the graph representation of the lower 48 United States (47, actually. I think I lost one somewhere…)

Representing maps in this way is a very important step. For one thing, it removes the issue of country shapes and border geometries. You could have a thousand different maps with differently shaped countries, but they might all have the same relationship between what borders what, and thus have the same four coloring. Notice that the positions of the nodes don’t even matter any more, only the connection relationships between the nodes. The graph representation encapsulates all the border information, and only that – all you need for the four coloring. We’ve reduced the problem from scribbling shapes with Crayons to connecting dots.

The other big reason this is important is because graphs are something Mathematicians know -a lot- about. We know how they behave, how they look, what kind of substructures you can expect in graphs of certain sizes and shapes. We know a lot, and we can apply that towards proving the Four Color Theorem.

But this representation allows us to tighten the problem further. The more mathematically we can represent the problem, the easier it will be to approach it. Using the construction above, every map has a graph representation, but not all graphs represent maps. In the example map above, and the graph representation of the US in the prompt, notice that none of the connections between nodes intersect. Graph representations of maps are characterized by this quality – spread them out on a plane, and you can arrange the nodes such that none of the connections intersect. As such, they are known as planar graphs. Every map has a representation as a planar graph, and every planar graph can be turned into a map.

We can now formulate the Four Color Theorem mathematically as the following: The Chromatic Number of any planar graph is at most four.

One other thing worth mentioning before we get deeper into the problem (I can’t think of a better segue for this section), we can tighten the problem ever so slightly more. Consider a given planar graph representing some map, and a coloring of that graph such that no two connected nodes share a color. Consider adding connections to the graph, though none that intersect old connections. Because we’re forming new connections between nodes, while we may need to use more colors to color the new graph (by connecting two nodes of the same color in the old graph), we cannot turn this into a graph that needs -fewer- colors to color. This amounts to adding border connections between countries.

Below we start with a map that results in a planar graph in the form of a square. By adding a connection between opposite corners of the square, we are changing the border relationship between the regions, and this results in an increased number of colors needed to color the map.

Notice too though, that the new coloring on the right, blue and red on top, then red and green on bottom, still colors the map on the left. The idea is that if the graph is colorable when new connections like that are added, it was -definitely- colorable before they were added.

By adding that new connection, we essentially made the graph harder to color. So, why not, for a given graph, add all the connections we can? These are ‘maximal planar graphs’. The ultimate result is that the area of the graph is partitioned into triangular faces (the square above became two triangles sharing an edge), and every node is connected to the most nodes it can be, making it as hard to color as possible. This corresponds to a map where each country is touching effectively every other country that it can. Maximum connectivity. Then, if these graphs, and thus maps, are colorable in four colors, then the same holds for all graphs, and thus maps.

As such, we only need to consider the chromatic numbers of planar, fully triangulated graphs.

But, with this nice formulation of the problem, how do we begin to approach it?

As I said, we know a lot about graphs. For instance, for planar triangulated graphs of certain sizes, we know what kind of substructures, shapes and relationships between nodes, must form as a result of that size.

The first, albeit incorrect, proofs of the four color theorem looked at individual nodes. The degree of a node is the number of nodes that node is connected to. For certain fully triangulated planar graphs, for example, you are guaranteed a node of degree four, that is, it is connected immediately to four other nodes around it. These proofs proceeded by coloring that node and the four around it, and then building the coloring outward into the rest of the graph in chains of alternating colors, using the non-intersecting properties of the graph connections to determine where those chains of colors must end up and how they affect the coloring of the rest of the graph. Very constructive, which I always find appealing. The proof then went on to induct on the degree of the nodes. The problem evidently comes in the case of nodes with degree five, where nothing is easy.

The next approach was taken by the proof that actually worked, the computer proof. I said earlier that they basically generated every possible map and colored it – not complete. As the previous proof looked at the individual nodes guaranteed to be in graphs of certain sizes, this proof looked at structures formed in the graph by subsets of the nodes. Shapes and forms guaranteed to occur in graphs, and thus arrangements of countries that can occur in maps. By generating all of these guaranteed shapes, and their colorings, they were able to induct on graphs that included these forms, and show all the graphs of interest to be four colorable. Relatively straight forward – except that the list of forms was nearly 2000 strong, in the 500 pages previously described. A more recent proof reduce the number of cases from near 2000 to a little over 600, but the logic of the proof remains almost impenetrable by humans. The question remains then, whether it would be easier to go through and check their proof by hand, or to come up with a completely new one.

Either way, the key to any proof of the four color theorem is a means by which the infinitude of possible graphs can be characterized and organized. Optimally, you would like to identify graph structures that would allow any graph in consideration to be reduced to a smaller case with a known four coloring. One method that I’m involved with for one of my professors (a long and tired story), involves characterizing the four coloring that results on the boundaries of graphs. For example, in any graph that is bound within three nodes, there are 24 ways of four coloring the boundary, any one of which is possible, no matter the structure of the graph. Far more interesting results follow on graphs bounded by four and five nodes, but I’m not sure how much I can really discuss here. Originally I had a longer exposition, but I’m not sure what all is appropriate to talk about given that this is someone else’s work as well.

All the same, it is a very interesting problem. I think so, at least : )