Four-Color Theorem

            The four-color theorem is a simple mathematical puzzle that was solved in the 1800’s by a mathematician named Willie Guthrie. “The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color” (Weisstein). Guthrie discovered this when he noticed that four colors suffice a map of England.  The Apple-Haken proof, developed in the 1970’s, needs a computer to solve it and mathematicians say that even though the hand written part of the proof is possible, it is extremely difficult and would take a very long time. Another mathematician named Heesch later developed the two main parts needed to write the ultimate proof, reducibility and discharging. Reducibility is an algorithm that transforms an equation into another equation, which can be seen in Euler’s formula I mention later. Discharging proves lemmas in structural graph theory. In the four-color theorem, discharging divides the already graph into smaller graphs from a specified list. I believe to understand this theorem is with an example like the one below.

            As you can see in the example, on the left we have a blank plane made up of rectangles and L-shaped shapes. On the right we have the same plane filled with 4 different colors, green, blue, yellow and red. If you look carefully at the picture you will see the same color does not touch the same color throughout the whole picture. Another popular example is an image of the continental United States. Using the same four colors, you can make a similar image to the example above.

            Even with this theorem being seemingly impossible to disprove with all the different shapes and maps, some mathematicians still found ways to prove this theorem wrong. Soon after Guthrie developed this theorem a man named Heawood proved another mathematician by the name Kempe wrong by using a map with eighteen faces. Although the theorem was proven back in the 1800’s people today still try and solve it in different ways with different planes, maps and less colors and anything in between. Appel and Haken’s proof that I mentioned in the first in the first paragraph used computers to solve try and prove their proof. “Although we could not guarantee that our work would lead to a proof of the four-color theorem. We were given well over 1,000 hours of computer time in what we feel was an admirable dis­play of faith in the value -of pure mathe­matical research” (Appel). In the 1970’s Kenneth Appel researched the four-color theorem like no one had before by using over 1,000 hours of computer research to find and alter the math of the theorem to prove it in many different ways. The math used to find figures that use the minimal amount of space, degrees and shapes to solve this theorem are beyond any of our levels but I will show you two examples that challenge this theorem.

These figures were developed with very precise angels and vertices that follow very strict rules. These strict rules are the rules of discharging, which I mentioned in the previous paragraph. Each vertex of the graph, which makes up the maps and graphs, has a charge. These charges are what helps mathematicians develop algorithms that deal with planar graphs. Even with all of these rules the theorem still is successful. Over the years mathematicians have developed shapes with many vertices that actually need more than four colors.

Euler’s formula was used for to solve the countries map problem with the four-color theorem. The formula f + v – e = 2 may seem simple and it is in ways but this was the basis formula for this theorem. An example that shows how to use Euler’s formula can be seen below. The v stands for the vertices, the e represents the edges shared by two regions and the f represents the faces or regions.

Now there are too many formulas for this theorem to give you one and say this is how you solve everything. Today’s formula use a different suffix g depending on the number of the colors you want to use to fill in the map. For example you can use six colors to suffice g= 0 and also five colors but once you try to solve for four colors is when it becomes extremely difficult. Simply going down to from five to four colors is what makes this “simple” theorem more complex than just filling in states with four colors.

When talking about the four-color theorem there is something special about it that most might forget to talk about. The four-color theorem not only applies to finite planar graphs but also infinite graphs. This was discovered when a mathematician combined a finite graph theorem with De Bruijn-Erdos theorem. This theorem states that every finite graph is an infinite graph k-colorable. With this theorem, the four-color theorem became the ultimate theorem for coloring any shape, map or graph.

"The Four Color Theorem." The Four Color Theorem. N.p., n.d. Web. 11 Nov. 2014.

Appel, Kenneth; Haken, Wolfgang (October 1977), Solution of the Four Color Map Problem, Scientific American 237 (4): 108–121

Weisstein, Eric W. "Four-Color Theorem." From Math World--A Wolfram Web Resource. http://mathworld.wolfram.com/Four-ColorTheorem.html