The four-color conjecture has been one of several unsolved mathematical problems. From 1852 to this day, practically every mathematician has studied the problem long and hard, but to no avail. The conjecture looks as though it has been solved by Wolfgang Haken and Kenneth Appel, both of the University of Illinois. They have used computer technology to prove the conjecture. The calculation itself goes on for about 1200 hours. The staggering length of the computation of the proof is what creates some controversy in the mathematical world. The Appel-Haken Theorem is based on numerous assumptions, “that there is an overwhelmingly great probability that their method of proof must succeed.” [3] It assumes that the theory itself is correct, but the theory itself is also an assumption. You can see why this issue has been wreaking havoc for many years.
It all started back in 1852 when Francis Guthrie was coloring a map of England. He wanted to know the least amount of colors, or chromatic number, it would take to color the map so no two adjacent regions are of the same color. He found the chromatic number to be four. He then studied arbitrary maps and wondered if all maps could be colored with four colors. Francis’ curiosity would be in the minds of all mathematicians to come. He then passed this question on to his brother, Frederick. He then submitted this to his professor Augustus deMorgan as a mathematical conjecture.
deMorgan was fascinated by the Four-Color problem and wrote in a letter to his colleague Sir William Rowan Hamilton the next day after seeing the conjecture. Hamilton was less enlightened by it, and never worked on it. It was through deMorgan that the Four-Color problem was made known, thus deMorgan has incorrectly been dubbed the originator of the problem.
Eventually the hype surrounding the conjecture died down in the early 1860’s. This down time, during which interest in the problem was minimal, only lasted about twenty years. A lawyer by the name of Alfred Bray Kempe proposed a solution in The American Journal of Mathematics Pure and Applied a year after an article by Arthur Cayley in the journal Nature rekindled interest in the topic. After a few observations by logician/mathematician Charles Peirce, the solution was considered to be valid.
The solution was shown to be valid and the mathematical world was at rest with the problem. Except for one man, Percy John Heawood. He studied Kempe’s “solution” and encountered a fallacy. This would create a scene in which it saw mathematicians scrambling for what they were working on, digging through garbage to find what they were scribbling.
Mathematicians went years without getting anything. Some would make headway, but an error would always pop up and they would have to start back at the beginning. Technology would give hope to some. This new technology was able to do problems faster than anyone had seen before. Mathematicians studying the problem would study computer science, hoping the computer would formulate a proof. Mathematicians known as purists strongly argued against this course of action.
Eventually it did, two computer scientists from the University of Illinois developed a program that would devise the proof. Wolfgang Haken and William Appel used procedures that the computer couldn’t handle so they brought in John Koch for some assistance. Koch, who once studied here at Bucknell, was in charge of reducibility calculations. Guthrie would be happy to know that a mere 124 years after he thought out the conjecture; an IBM 360 in Urbana, Illinois would prove it.
Some would think that this concludes the history of the proof, but there is still an untold portion. In 1994, computer scientists weren’t happy with the 1200 hours it took to prove the conjecture. The simplified proof, which was developed by Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas, was presented by Seymour. It compresses the computation time from 1200 to 12 hours. Although this breakthrough was considered to be a significant step, the question of a “computer-free proof” is still at large.
Francis Guthrie was born on January 22, 1831 in London, England. He lived most of his life in South Africa, where he died on October 19, 1899 at the age of 68, just nine months out of retirement. He studied at the University College in London, where he received a bachelor degree of Arts in 1850. He attended law school and received his bachelor of laws in 1852 with first class honors.
In April of 1861, Guthrie decided to accept a job at the Graaf-Reinet College in the Cape Colony of South Africa as a professor of mathematics. He was considered to be a very hard worker, but he was personified as being warm-hearted, humorous, patient, and unpretentious. An anonymous colleague noted that he was more concerned with his students who showed their love for mathematics rather than his lectures.
In 1875, he stepped down from his professorship at Graaf-Reinet and moved to Cape Town, where he met up with a friend who was also interested in botany. Together they traveled to England where they studied botany, in particular, the flora of the Cape region. He also gave public lectures on botany that were inspired by John Lindley, an old acquaintance from his days back in London.
The diversity of Guthrie’s knowledge was evident when he delivered a lecture titled, “The Heat of the Sun in South Africa.” He pointed out in his introduction that it must be probable for energy from the sun be able to be transformed into mechanical power. He also was interested in aeronautics. He was involved in the development of the first aircraft. He was dubbed the inventor of the first flying machine. Unfortunately, no documentation of his work exists.
He then moved on to a teaching job at South Africa College in Cape Town. He taught there from 1878 until 1899 when he retired. His mathematical writings are “not outstanding, from the context and quantity vantage points. We are familiar only with his ideas that predominantly deal with problems involved in elementary algebra and physics.
Besides his connection to the Four-Color Theorem, Guthrie established a name for himself in the botanical field. His name is used for “botanical nomenclature” on two plants with the names of Guthriea capensis and Erica Guthiei. His widow dedicated a herbarium in Cape Town to him, after his death.
In class, we proved the Six Color Theorem, which states
that any planar map can be colored using six colors.
A graph is colored if no two vertices that have a common
edge are of the same color when all vertices are colored.
We start with a lemma that states: [It is necessary
to show that at least one vertex of a planar graph has order five
or less.]
Every
planar graph contains at least one vertex of order five or less.
We will assume the opposite of the lemma, that no vertex on the graph has order five or less. We need to assume that we have a graph of this. We know that the sum of the order of all faces is greater than or equal to 3f. We also know that the sum of the order of all faces is equal to 2e. Applying this equation with the first inequality, we find that f is less than or equal to 2e/3.
We then need to suppose that every vertex has at least order 6. From this we get that the sum of the order of all vertices is greater than or equal to 6v. We also know that the sum of the orders of all vertices is equal to 2e. The combination of these two statements yields v is less than or equal to e/3.
These two inequalities will now be applied to Euler’s formula to see if the lemma holds true. Euler’s formula says that v-e+f = 2. We replace v and f using the above inequalities to find that 3e-e+2e/3 is less than or equal to 0. This proves the negation of lemma to be false, so the lemma itself is true.
To complete the proof we will use graphs and the four steps listed below. [7]
Step 1: Pick a vertex with order less than or equal to 5.
Step 2: Delete the vertex and all edges leading into it, do this until 6 vertices remain.
Step 3: Color the six remaining vertices using six colors.
Step 4: One by one, starting with the vertex you removed last, put them back on the graph with the corresponding edges. Each time, color the vertex with a color that isn’t used on the adjacent vertices.
Here is an example, step by step, of the Six-Color Theorem.
Another problem to be considered is the proof of the Five-color theorem. It is not necessary to go through the procedure of the proof, since the proof has very similar characteristics to the Six-color proof. I will simply point out the main differences and important precautions that need to be watched for when five coloring.
As mentioned, the proof is done as in the six-color theorem. An additional note, worth pointing out, is that we are trying to reduce the graph to four vertices by removing vertices and their corresponding edges one by one. After narrowing the graph down to four vertices, we color them in using four different colors. Furthermore, when we begin reinstalling vertices and edges after the removal process, we still need to be able to color the graph with four colors; by this we mean that the reintroduced vertex cannot have a similar edge with at least one of the original four vertices. The graph always has to be four colored until the last vertex is installed. This vertex takes on the fifth color and thus, you have the five-color theorem.
[6, p130]
Coloring is a big problem in mathematics. Although it seems relatively easy, it still boggles the mind of every mathematician for 150 years. I think that these problems are good because they seem so easy at first, but once you get into the problem, it’s more than just coloring. There is a lot of mathematics behind coloring a map. These problems are important because they can be applied to areas outside of cartography.
For example, it can be used to determine the best meeting times for groups. Let’s suppose we have a company that has committees and members are in several committees. If we needed to set up a schedule of times that the committees would meet, we could use our coloring schemes. Each committee is a region on the graph and the colors are meeting times. Then two committees would be adjacent if members were belonged to both. Then the graph would be colored and the times would be situated where there wouldn’t be a conflict. This signifies how vastly important graph coloring is in the mathematical world.
Bibliography
[1] The Four Color Conjecture, Meredythe Lee Gray, Honors Thesis from 1974
[2] The Four Color Theorem, Rudolf and Gerda Pritsch, copyright 1998 Springer-Verlay, New York, NY
[3] http://math.ucsd.edu/~rellis/comb/fct.html
[4] http://www.humboldt.edu/~mef2/color.html
[5] Packet from class on Four Color Problem, Ulrich Daepp, class handout.
[6] Graph Theory, Frank Harary, Addison-Wesley, Readinge, Ma. Copyright 1972
