Four color theorem

(PD) Sketch: Thomas Wright Sulcer
Try it: ANY map of provinces, such as this one of France, can be colored in by using only four colors. Why? Mathematicians figured out the puzzle with the aid of computers.

The four color theorem, sometimes known as the four color map theorem or Guthrie's problem, is a problem in cartography and mathematics. It had been noticed that it only required four colors to fill in the different contiguous shapes on a map of regions or countries or provinces in a flat surface known as a plane such that no two adjacent regions with a common boundary had the same color. But proving this proposition proved extraordinarily difficult, and it required analysis by high-powered computers before the problem could be solved. In mathematical history, there had been numerous attempts to prove the supposition, but these so-called proofs turned out to be flawed. There had been accepted proofs that a map could be colored in using more colors than four, such as six or five, but proving that only four colors were required was not done successfully until 1976 by mathematicians Appel and Haken, although some mathematicians do not accept it since parts of the proof consisted of an analysis of discrete cases by a computer. But, at the present time, the proof remains viable, and was confirmed independently by Robertson and Thomas in association with other mathematicians in 1996–1998 who have offered a simpler version of the proof, but it is still complex, even for advanced mathematicians. It is possible that an even simpler, more elegant, proof will someday be discovered, but many mathematicians think that a shorter, more elegant and simple proof is impossible.

(PD) Sketch: Thomas Wright Sulcer
While the four color problem is less interesting to cartographers, it can help other areas such as cell tower placement. If each cell tower broadcast channel is like a color, and channel–colors are limited to four, then the problem of where to position broadcast towers for maximum coverage and minimal cost is the same as the four-color problem. The challenge? Eliminate non-coverage spots (red) along the highway. In places where multiple channels overlap (dark blue), the channels must be different––colors must be different, so the cell phone signal can be handed off to a different channel.

While the question isn't necessarily important to mapmakers since they often use a wide range of colors, the question has implications in related disciplines. For example, cell phone companies need to assign separate channels to two transmitters to ensure that there isn't interference when their ranges overlap. But at the same time, they'd like to limit the number of transmitters while avoiding situations when some zones are not covered by any transmitter. Therefore, to save money, how can they assign locations for cell phone towers or transmitters efficiently to minimize the number of towers, yet cover an area thoroughly without the towers interfering with each other? The problem is the same as the four color problem: if transmitters are like dots or nodes connected by lines, then it's possible to imagine the transmission channels as if they're colors assigned to the nodes. Surprise: it's the same problem. But it's a hard problem, since the four color problem doesn't have to work for merely existing maps, but all possible and conceivable maps, so that knowing you can color in some particular map using only four colors is not helpful. What's needed is an argument that can prove, beyond doubt, that the four color solution will work for all possible maps.

Background

(PD) Sketch: Thomas Wright Sulcer
Step 1: This is a DIFFICULT problem in two-dimensional space. Borders wander. It's necessary to translate the problem into something workable.

(PD) Sketch: Thomas Wright Sulcer
Step 2: Place a point or dot or node in each contiguous province in Germany. Put the points anywhere you wish. If two provinces share a common border, then draw a line between the two points. No common boundary? Then don't draw a line.

(PD) Sketch: Thomas Wright Sulcer
Step 3: A redefined problem. Instead of a complex map with many wandering boundaries, it's a simpler problem of nodes. If two nodes are connected by a line, then they can't be the same color. Mathematicians used this kind of reasoning to make an extremely complex problem much more manageable.

The problem was introduced formally in 1852 by botanist Francis Guthrie who examined maps of counties in England. By 1878, it was widely known throughout the mathematical community. But soon thereafter, mistaken proofs were offered, and some of these were accepted by the community until disproved. For example, in 1879, Alfred Bray Kempe offered a proof in the American Journal of Mathematics which was accepted for a decade. People believed it. Kempe was knighted. He was made a Fellow of the Royal Society in England. But, eleven years later, an error was discovered by Percy John Heawood, and the Kempe proof was disproved.

The regions of a map must be contiguous, so it's not acceptable to insist on each country or region having two entirely separate, and non-touching, parts; for example, while the island of Corsica belongs to France, the two areas are geographically separate. Further, it's not enough for two regions to touch at only one point; rather, the two regions must share a boundary which is a line consisting of more than one point. If regions could touch at only one point, then it's theoretically possible to devise a map needing more than four colors.

The difficulty with proving the four color problem was that there weren't a few theorems which could be neatly stitched together in an elegant and simple proof; rather, solving the problem required checking "many, many specially constructed maps" and then determining which maps needed to be checked, and this entire process lets open the floodgates for mistakes. It required computers to handle much of the checking. Initially there was resistance to the idea of using computers to assist in a mathematical proof, but over time, this resistance has broken down as computers have become more ubiquitous and better accepted.

The problem has attracted much attention from amateurs. There appear to be some obvious ways to solve the problem, but which have subtle errors, and it takes professional mathematicians to spot these errors. According to Keith Devlin, "professional mathematicians grew used to receiving claimed proofs from amateurs who would often remain convinced their solution was correct even after the error was pointed out to them."

A key to solving the proof came with a new way of thinking about the problem. It's difficult to think in terms of geographic space. But the problem can be translated slightly, with just as much philosophical rigor, by imagining that there is a map with regions. Inside each region you can place a single point––a dot––or sometimes called a node. But think of the dot or node as a capital city, like Paris in France. The dot can be placed anywhere within the region (and the proofs insist that they indeed can be placed anywhere within any region). Then, think of another country next to France, such as Belgium. Belgium touches France, that is, the two countries share a common border. If you place a dot inside Belgium––its capital city of Brussels––then you can draw a line from Paris to Brussels such that it doesn't go to any third country (eg Germany), but goes directly from France to Belgium, from capital to capital, like a direct railroad link. It crosses exactly ONE border––the border between France and Belgium. It doesn't cross the border between France and Germany, for example. The idea, then, is that the two capitals must have different colors––one color for Paris, a different color for Brussels. Then, the problem of geography can be rethought into a problem of geometry, essentially. Mathematician Keith Devlin explained:

Indeed, the problem of coloring the map (in the sense of Guthrie's problem) can be reformulated in terms of coloring the network: color the nodes of the network in such a way that any two nodes which are connected together must have different colors. If all networks can be so colored using four colors, so can all maps, and vice versa.Keith Devlin

Now, the task is to prove the network version of the four color problem, but come at the problem backwards to find a contradiction. Assume that there is a network that cannot be colored with four colors; describe this network (if possible) and deduce a contradiction. Find a network with the least number of nodes. Then, with this constructed, see if it's possible to remove any particular node (or capital city) without altering the number of colors needed to color the network. But the new network will then have one fewer node than the network with the least possible nodes. If this fact is combined with the fact that the initial network was the smallest one possible that could not be colored with four colors, then the logical implication is that the new network can be colored with four colors. But this contradicts the fact that the original map can be colored with four colors.

So, what happens, then, is that the problem is redefined to one of how to describe the processes used to "reduce a given network to one with fewer nodes" but "without reducing the number of colors necessary to color the network". That is, a counter-example must contain at least one node (or capital city) that can be removed as described above. But showing this requires computer assistance.

Appel and Haken

To do this, mathematicians Kenneth Appel and Wolfgang Haken of the University of Illinois had to identify 1476 different ways that a node could be appropriately removed. And for each case, they had to show that any minimal counterexample must contain at least one node of the kind above. This is a lot of work. This problem required 1200 hours of computer time in which billions of calculations were performed. Further, the mathematicians had to analyze by hand some "10,000 portions of networks." They began in 1972. They finished in 1976. But their discoveries were marked with some skepticism, and it eventually led to the publication in 1989 explaining their proof, with hundreds of pages of microfiche detailing diagrams.

Robertson, Sanders, Thomas, Chudnovsky

In a separate effort, mathematicians tried to confirm the Appel and Haken proof, but stumbled upon a way to reduce the problem further, making it less complex, although the proof was still highly complex and required computer assistance as well. Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas in 1996–1998, in conjunction with other mathematicians, found a more efficient method, but which also used a computer, but followed a trajectory similar in some ways to the Appel and Haken proof. The new group figured out there was a set of 633 so-called configurations that were reducible, meaning that with these configurations, it was impossible to choose colors within these shapes that would require more than four colors. Then they applied various algorithms showing that these configurations suggested that no minimal counter-examples were possible, and therefore offered a slightly less complex (but still difficult) proof. Generally, work by other mathematicians suggests that the mathematical community is satisfied that the so-called unsolvable Four Color Problem has finally been solved with an acceptable mathematical proof.

Proof

If planar regions have more than three edges for their boundaries, it's possible to add more edges without having to add more vertices. This results in a so-called graph that is a triangulated graph. If this graph can be colored using only four colors or fewer colors, then the original untriangulated graph can be colored with only four or fewer colors, since the same coloring is acceptable if the edges are not there. Therefore, all we have to do is prove the four color theorem for triangulated graphs; we don't need prove it for all planar graphs.

Suppose v is how many vertices or corners there are. Suppose e is how many edges or sides there are. Suppose f is how many regions there are. A formula by Euler states that v − e + f = 2. Since each edge is shared by two regions, then 2e = 3f. This suggests that 6v − 2e = 12. Regarding the vertices, the number of edges abutting a given vertex is known as the degree. If the degree is n and v is the number of vertices, then vn is the number of vertices of degree n, and let's call D the maximum degree of any vertex.

$6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.$

Suppose there is a graph which requires at least five colors. If this is true, then there should be a minimal version of this graph in which removing any one vertex will make the graph able to be colored by only four colors, of four-colorable.

Let's denote this graph G. G cannot have a vertex of degree 3 or less, because if d(v) is less than or equal to three, then we can take out the v from G, use four colors on the smaller graph, then put back in the v and extend the four-coloring by using a color different from its neighbors. It's impossible to have any graph G with a degree of four or greater.

(PD) Sketch: Thomas Wright Sulcer
Here's a shape requiring more than four colors. There's no way to fill in the shape with only four colors without having some of the same colors touch. Does this diagram disprove the four color theorem? No. The diagram breaks a key rule which is that every boundary must be a line, not just a point. Notice that many of the triangular shapes in the middle have a common boundary on the center-left which is only a point (not a line) so this diagram is disqualified, and the four color theorem still stands.

Suppose we take out the vertex v, four-color the remaining vertices. If all four neighbors of v are different colors, say blue, green, red and yellow, we look for a Kempe chain of alternating path of vertices colored blue and red which join the blue and red neighbors. There may be a Kempe chain joining the green and yellow neighbors but not both because these two paths must intersect, which means that the vertex where green and yellow join cannot be colored. If the blue and red neighbors are not chained together, then one can explore all possible blue-red alternating paths and then reverse the colors blue and red on all of these vertices. Result? All valid coloring with four-colors, allowing us to add v back in and be colored blue. This is called a reducible configuration.

The difficulty comes with a degree of 5 in the vertex. It's not enough to merely remove a vertex, but it's necessary to consider a variety of different configurations which are connected subgraphs of G with the degree of each vertex specified.

If, however, at least one of a set of configurations must occur somewhere in G, that set is called unavoidable. The easy part of the proof showed that versions with fewer vertices were all reducible, that is, a single vertex of degree 1 was reducible, a single vertex of degree 2 was reducible, and so forth, all the way up to degree 4. The problem was showing that a single vertex of degree 5 was reducible. This would clinch the proof.

Since G is triangular, then the degree of each vertex in a configuration is a known number. Further, all edges internal to the configuration are known as well. And, the number of vertices in G adjacent to a specific configuration is a fixed number as well. All of these terms are joined in a sort of ring or cycle, that is, the vertices can be thought of as having a ring of a configuration. If a particular configuration has, say, j vertices, then it can be called a j-ring configuration, and the configuration, together with its ring can be called a ringed configuration. It's possible to list out all separate four-colorings of any given ring; they termed any coloring that can be extended without changing anything to the coloring by the term initially good. The surrounding graph must be methodically recolored to change the ring's colors into a good one. This was easy when there were only four neighbors, but when there were more, this becomes more difficult. It's this complexity which requires the use of high-powered computers. In other words, there are a great many particular four-color variants of each ring, and this requires computing power to analyze each one.

The next step is figuring out which set of configurations are unavoidable, that is, which ones can be reduced by this procedure. The method was called discharging and considers the planar graph as an entire system similar to an electrical network, such that the positive and negative charges are distributed among the different vertices so that the total result is positive.

$\sum _{i=1}^{D}(6-i)v_{i}=12.$

Assign each vertex an initial charge of 6-deg(v). Then one flows the charge by methodically redistributing the charge from a vertex to its neighboring vertices according to a set of rules determined by the discharging procedure. Since charge is so-called preserved, some vertices still have a positive charge. The rules restrict the possibilities for configurations of positively-charged vertices, so enumerating all such possible configurations renders what is called an unavoidable set. One keeps going with this while one or more members of the unavoidable set remain reducible; while this is the case, then the discharging procedure is modified to eliminate this (and it allows other configurations to take their place). The discharging procedure was extremely complex. Appel and Haken described this procedure is a 400-page volume. It was still possible to check each configuration mechanically to ensure that it was, in fact, reducible, and this was done in a scientific checking process known as peer review, and it was done, although it took place over a period of years. The results confirmed that the proof was solid.