Go to Math Dept Main Page | Go to Mission College Main Page

This paper was written as an assignment for Ian Walton's Math G - Math for liberal Arts Students - at Mission College. If you use material from this paper, please acknowledge it.

To explore other such papers go to the Math G Projects Page.
 

How many colors are required to color any map so that no countries with common borders are the same color? It is generally held that four colors, for any flat map, will suffice. But a belief that is commonly held and easily observed, is not a mathematical certainty. Nor does the simplicity of a question reflect the ease with which the answer can be proven.

The mathematical evidence to create a valid proof that four colors are all that is required had evaded mathematicians for nearly 140 years. What became known as the Four Color Conjecture has been the cause of great fascination and frustration. It has also been the stimulus for new ideas in topology, knot theory, and the concept of mathematical proof.

Historical Overview:

The question was originally posed by Francis Guthrie, a former student of the famous mathematician Augustus De Morgan, in 1852. Although Francis moved on to study law, his brother Frederick Guthrie had become a student of De Morgan. Francis Guthrie presented his work on the idea to his brother asking that he pass it along to De Morgan.

De Morgan, unable to validate Francis Guthrieís theory, passed the problem along to Sir William Rowan Hamilton. The problem described by De Morgan to Hamilton was:

A student of mine asked me today to give him a reason for a fact which I did not know was a fact - and do not yet. He says that if a figure be anyhow divided and the compartments differently colored so that figures with any portion of common boundry line are differently coloured - four colours may be wanted, but not more - the following is the case in which four colours are wanted. Query cannot a necessity for a five or more be invented.

Although Hamilton was unable to create a map that required five colors, he was also unable to prove that no such map existed.

In 1879 Alfred Bay Kempe publishes a proof using an argument known as ìthe method of Kempe chains.î After more than twenty-five years, the Four Color Conjecture became the Four Color Theorem.

In 1890 The Four Color Theorem, once again, became the Four Color Conjecture when Percy John Heawood revealed errors in Kempeís proof. Kempe was unable to correct these errors.

Heawood continued to work on the problem, in various forms, throughout his life. He was a major contributor to the Four Color Theorem and itís eventual proof. He demonstrated that every map can be five colored as well as proving that if the number of edges surrounding each region is divisible by three, then the regions all require a maximum of four colors. His other contributions include what is now known as the ìHeawood estimateî and notable advances in the study of number of colors required to color other surfaces (non-planar).

Overcoming the Difficulties of Proof

In 1879 a paper by Arthur Cayley was published by the Royal Geographical Society. It explained the difficulties involved in attempting to provide a valid proof of the Four Color Conjecture. Evidence in this paper was undoubtedly abundant.

One of the most basic obstacles to be overcome in creating a valid proof is that there are infinitely many maps that can be drawn, and therefore infinitely many examples to be tested. This is remedied through the use of proof through counter examples. A counter example to the Four Color Conjecture would require that a map, within the parameters of the conjecture, be created which required more than four colors.

In attempting to create counterexamples, it becomes apparent that the shapes of the regions have little impact on the problem. It is the arrangement of adjoining regions that is important.

This discovery allowed graphs to be used to represent various map configurations. Placing a vertex at each capitolís border and then connecting the capitols of any countries with a common border creates a graph. Using graphs also allows configurations to be systematically created and analyzed, as required for a valid proof.

Although the original question is fairly clear, restrictions to create mathematical accuracy were added. In common understanding these restrictions include the ideas that countries must be connected by regions, colonies spread across the map are not to be considered.

Additionally a single shared point does not constitute a common border. In this case maps could be arraigned like wedges of a pie and would necessitate as many colors as wedges (regions). Figure 1.

Although I was unable to locate anything titled ìTheorem 1," the two following Theorems are the mathematical descriptions of the conjecture to be proven. They also include, as a result of their preciseness, the restrictions noted above.

Theorem 2 of the Four Color Theorem states: ìEvery planar map with regions of simple borders can be coloured with 4 colours in such a way that no two regions sharing a non-zero length border have the same colour.î

Theorem 3 states ìEvery loopless planar graph admits avertex-colouring with at most four different colours.î

Modern Proofs

In 1976 two mathematicians at the University of Illinois, proved the Four Color Theorem (Theorem 3) through the use of computers. The proof achieved by Kenneth Appel and Wolfgang Haken based their methods of reducibility on the Kempe chains. Their methodology also utilized the ideas developed by Heinrich Heesch; the infinite set of maps could be constructed from a finite set of maps. Using a ìbuilding blockî concept they constructed a set of 1500 unavoidable configurations. The details of the final proof were worked through using 1200 hours of computer time. Initially this proof was met with some skepticism as it was the first proof which could not be verified directly by ìhand.î This was a significant deviation from the traditional verification and validation process. The available literature is somewhat ambivalent. Appel and Hakenís work is referred to as a ìproof,î and the Four Color Conjecture is now noted as the Four Color Theorem, denoting some finality in the problem. Yet despite independent verification through computers and published details of the proof, it seems the proof continued to be held in lesser regards.

Despite the scrutiny and questions of it being ìsilicon proof,î the Appel and Haken proof was never found to be mathematically flawed. Yet the search for a methodical and efficient, if not ìhandî verifiable proof continued.

Sometime in 1995, a new proof was presented. In the more compact and refined proof given by Neil Robertson, Paul Seymore, Robin Thomas and Daniel Sanders reference is made to the Appel-Haken proof being ìnot completely satisfactory.î This cloud of doubt appears to be, at least in part, the motivation for completing a new proof. The authors of the new proof also reference the history of disproved theorems to this problem and a desire to lay all questions to rest. According to the summary of the Robertson, Seymore, Thomas and Sanders proof, not even the part of the Appel-Haken proof which is supposedly ìhand-checkableî had ever been verified in its entirety due to its complexity and the tediousness of the task.

The authors of the new proof indicate ìThe basic idea of the proof is the same as Appel and Hakenís.î Some of the key differences they note are:

The use of ìdischargingîfirst suggested by Heesch.

A significantly reduced ìunavoidableî set size - 633 compared to 1476 set of Appel and Haken.

ìDischargingî method using 32 rules where Appel and Haken used 300+

A quadratic algorithm to four-color planar graphs instead of a quartic algorithm

Only integer math was used to prevent round off and floating decimal errors.

(This information may be provided for just clarity, or in comparison to the Appel-Haken proof.)

Key Concepts in the Modern Proofs

One of the concepts used in the development of proof for the Four Colour Theorem was the use of the ìgreedyî or ìsingle mindedî algorithm. The purpose of an algorithm of this type is to perform a single task over and over (color the area of a graph) until it can no longer repeat that single task.

The Kempe Method of chains is described by the MacTutor Math online mathematics archive at Saint Andrews, in a document called ìThe Four Colour Theoremî as the following:

If we have a map in which every region is coloured red, green, blue or yellow except one, say X. If this final region X is not surrounded by regions of all four colours there is a color left for X. Hence suppose that regions of all four colours surround X. If X is surrounded by regions A, B, C, D in order, coloured red, yellow, green and blue then there are two cases to consider.

(i) There is no chain of adjacent regions from A to C alternately coloured red and green.

(ii) There is a chain of adjacent regions from A to C alternately coloured red and green.

If (i) holds there is no problem. Change A to green, and then interchange the colour of the red/green regions in the chain joining A. Since C is not in the chain it remains green and there is now no red region adjacent to X. Colour X red.

If (ii) holds then there can be no chain of yellow/blue adjacent regions from B to D [It couldnít cross the chain of red/green regions] Hence property (i) holds for B and D and we change colours as above.

Graphs are created from maps by representing regions as vertices that are joined by edges if regions are adjacent resulting in a graph which is then ìplanar.î Areas of the graph are then ìtriangulatedî by adding edges to any non-triangular regions. The set of configurations used in the analysis for the proof are those parts of a traingulations contained in a circuit.

Edges, vertices, triangles and other variations are assigned numerical values and assigned degrees. Configurations are then compared to determine if they are isomorphic.

Discharging rules involve assigning charges to each vertex and redistributing. If the degree of the vertices is between 6 and 12 inclusively, it can be ìhand verified.î The others require the use of complex proofs written in formal computer language.

The 633 configurations used in the newest proof were all proven to be ìreducibleî which means that no configuration with this property can appear in a minimal counter example. This concept was originally developed by Heesch. Figure below contains 17 of the 633 reducible figures from the proof summary. All of the figures used can be viewed by downloading an ftp file at: http://www.math.gatech.edu/~thomas/FC/fourcolor.html#Algorithm

Summary

The Four Color Theorem has opened the door to many coloring questions and answers. Mathematicians have proven that the maximum number of colors required for any map drawn on a torus is seven and a double torus is eight. Carsten Thomassen, a graph theorist at the Technical University of Denmark, has demonstrated that each type of surface, other than the plane, has a finite list of maps that require six colors.

More importantly, The Four Color Theorem has changed the way that mathematical proof is viewed. The Four Color Theorem is the first proof that used a computer and was not actually able to be verified by hand. In the summary of the most recent Four Color Theorem proof the authors note:

In particular, we have not proved the correctness of the compiler we compiled our programs on, nor have we have not proved the infallibility of the hardware we ran our programs on. These have to be taken on faith, and are conceivably a source of error. However, from a practical point of view, the chance of a computer error that appears consistently in exactly the same way on all runs of our programs on all the compilers... is infinitesimally small compared to the chance of a human error during the same amount of case-checking.

As with the search for resolution of other questions in mathematics, the process of solving the Four Color Problem opened the door to many new thoughts and ideas. One of those ideas is the use of computers to solve and prove mathematical puzzles that have yet to be resolved ìby hand.î Will the Four Color Theorem usher in a new form of proof? It is hard to imagine otherwise. The use of a computer, and more importantly, the inability to verify and validate in the traditional methods, was met with resistance. But it also opens the door to new and inventive ways to ponder other unresolved problems.

The internet, I believe, will also play a profound role in the changing face of problem solving and validation. By placing the new Four Color Theorem proof on the internet, a proof which can be downloaded in less than twenty minutes, are the authors in some way issuing a challenge?

The proof is now available for scrutiny, improvement as well as expansion of the ideas contained therein by the entire world.

As limited as my mathematical experiences are, I feel fairly certain, that the Four Color Theorem and computer proof, will prove as fuel for more questions, discovery and research.

Bibliography

ìAn Overview on Graph Theory.î Leibniz Laboratory, The Graph Theory Team

http://www-leibniz.imag.fr/GRAPH/english/overview.html (5/1/99)

Devlin, Keith. ìDevlinís Angle.î MAA online. September 1998.

http://www.maa.org/devlin/devlin_9_98.html (4/29/99)

ìKnot Theoryî Ideas, Concepts and Definitions. MegaMath

http://www.cs.uidaho.edu/~casey931/mega-math/gloss/knots/knots.html (5/1/99)

ìProof, Mathematical,î Microsoft Encarta 98 Encyclopedia. 1993 - 1997.

ìThe Four Colour theorem.î The MacTutor History of Mathematics archive

University of Saint Andrews. September 1996 http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/The_four_colour_theorem.html (4/25/99)

ìThe Most Colorful Math of Allî MegaMath

http://www.cs.uidaho.edu/~casey931/mega-math/workbk/map/map.html (4/25/99)

ìThe Four Color Problem and its connection to South African Floraî

http://www.uwinnipeg.ca/~ooellerm/guthrie/FourColor.html#Cayley (4/25/99)

Dr. Math. The Math Forum - Questions & Answers from our Archives. Articles:

Four Color Theorem 8/27/96 http://forum.swarthmore.edu/dr.math/problems/satyadeeppc.8.21.96.html (5/5/99)

Four Color Theorem 4/3/95

http://forum.swarthmore.edu/dr.math/problems/fourcolormap.html (4/29/99)

The Four Color Map Problem 11/12/97

http://forum.swarthmore.edu/dr.math/problems/lisa11.11.97.html (4/29/99)

Jenson, Tommy R. and Bjarne Toft. ìGraph Coloring Problems.î The Archive.

University of Southern Denmark 1/28/99

http://www.imada.sdu.dk/Research/Graphcol (4/25/99)

Peterson, Ivars. ìIvars Petersonís Mathlandî. Science News Online. 1/4/97

http://www.sciencenews.org/sn_arc97/1_4_97/mathland.htm (5/1/99)

Robertson, Neil and Daniel Sanders, Paul Seymour and Robin Thomas.

ìThe Four Color Theoremî 9/13/95

http://www.math.gatech.edu/~thomas/FC/fourcolor.html#Algorithm (4/29/99)

Robertson, Neil and Daniel P.Sanders, Paul Seymour, Robin Thomas.

ìA New Proof of the Four-Colour Theorem.î

The American Mathematical Society Journal.

http://www-irma.u-strasbg.fr/EMIS/journals/ERA-AMS/1996-01-003/1996-01-003.html (5/1/99)

Miller, Charles D, Vern E.Heeren and E John Hornsby, JR. Mathematical Ideas.

(8^th Ed.) Menlo Park: 1998

ìTopology,î Microsoft Encarta 98 Encycolpedia 1993 - 1997.

Basic Concepts

Algorithm:

A precise, step by step problem solving procedure.

Conjecture:

Inference based on incomplete evidence.

Homeomorphic

Two figures or point sets are homeomorphic if a one-to-one correspondence that is continuous in both directions exists between them.

Knot theory:

Branch of topology that deals with closed curves that can be twisted and deformed in three dimensional space, but not torn.

Polynomial:

Any finite sum (or difference) of terms.

Proof:

Evidence or argument that establishes an assertion or conjecture as true.

Theorem:

A proposition in mathematics that has been shown to be true.

Quadratic:

Of or containing quantities of the second degree.

Quadratic equation:

One variable is a polynomial equation of degree two.

Quartic Equation

Equation of the fourth degree - with a leading term of x^4.

Topology:

Branch of mathematics that explores properties of geometrical figures. Known as ìrubber sheetî or ìrubber bandî geometry. Concerned with relative position and general shape (as opposed to absolute position, parallel lines and distance).

Triangulation:

To measure using trigonometry.

Trigonometry:

The study of relationships between the sides and angles of triangles.

Graph Concepts

Complete graph:

A graph in which every pair of vertices is connected by an edge.

Cycle/Circuit:

Path which begins and ends on same vertex.

Degree:

The degree of a vertex in a graph is the number of edges that touch it.

Edge:

Lines connecting vertices.

Path:

Route traveled along edges.

Planar Graph:

A graph that can be drawn so that the edges touch each other only where they meet at the vertices.

Size:

The size of a graph is the number of vertices that it has.

Vertex, vertices:

a) the point at which the sides of an angle intersect

b) the point on a triangle opposite to and farthest away from its base.

This paper was written as an assignment for Ian Walton's Math G - Math for liberal Arts Students - at Mission College. If you use material from this paper, please acknowledge it.