Abstract

This paper is a discussion on the interesting history of the Four Color Theorem. The discussion will bring to light the numerous proofs and the controversies that arose from them, but first a brief review will be given as to what the Four Color Theorem actually is.

Introduction

The problem of proving the Four Color Theorem has a notable history, details of which I found both throughout the World Wide Web and in Keneth H. Rosen's Discrete Mathematics and Its Applications: fifth edition. In Ashay Dharwadker's A New Proof of The Four Color Theorem, he introduces the theorem like this:

"In colouring a geographical map it is customary to give different colours to any two countries that have a segment of their boundaries in common. It has been found empirically that any map, no matter how many countries it contains nor how they are situated, can be so coloured by using only four different colours. The map of India requires four colours in the states bordering Madhya Pradesh (see Figure 5). The fact that no map was ever found whose colouring requires more than four colours suggests the mathematical theorem."

Rosen States that each map in the plane can be represented as a graph. To illustrate this relation, each region of the map is mapped to a vertex in a graph. Where two regions share a border, that border corresponds to an edge between the vertices who respresent those regions. He makes it clear, that maps of regions such as the Four Corners Region of the U.S. aren't considered adjacent if the regions share only one point. This resulting graph is called a dual graph of the map(see Figure 7).

To try and color/label the regions of a map, is equivalent to trying to color the vertices of a dual graph such that no two adjacent vertices of the dual graph have the same color/labeling. To make all of this more understandable, refer to the definitions below.

back to top.

Definitions

Definition 1:

A simple graph consists of , a nonempty set of vertices $\text{[math]}$ , and , a set of unordered pairs of distinct elements of V called edges.

Definition 2:

Two vertices and in an udirected graph are called adjacent ( or neighbors) in if is an edge of .

Definition 3:

A graph is called planar if it can be drawn in the plane without any edges crossing (where a crossing of edges is the intersection of the lines or arcs representing them at a pint other than their common endpoint). Such a drawing is called a planar representation of the graph (see figures 1 and 2).

Definition 4:

A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.

Definition 5:

The chromatic number of a graph is the least number of colors needed for a coloring of this graph.

back to top.

Four Color Theorem

The question of what the least number of colors needed to color a map such that no two adjacent regions are the same color has been studied for over 100 years. For a while the answer was merely a conjecture but then when it was proved it became one of the most famous theorems in mathematics. The theorem is known as the Four Color Theorem.

Rosen states the theorem as follows:

The chromatic number (Defn. 5) of a planar graph (Defn. 3) is no more than four.

Dharwadker did not define chromatic number, so he states the theorem with out it, as follows:

For any subdivision of the plane into non-overlapping regions, it is always possible to mark each of the regions with one of the numbers 0, 1, 2, 3, in such a way that no two adjacent regions receive the same number.

History of The Theorem

The Four Color Theorem is shrouded in confusion and controversy. It is believed to have been conjectured in the 1850s. Some feel it can be traced back to a letter written by Augustus DeMorgan to Sir William Rowan Hamilton, who ended up just dismissing it because it had nothing to do with his interest at the time, quaternions. Dharwadker believes it was proposed by Möbius in 1840, but Rosen believes it began with Francis Guthrie.

In 1852 Francis Guthrie, a former student of Augustus De Morgan, observed that the counties of England could be colored using four colors so that no adjacent counties were assigned the same color. From this observation he conjectured that the Four Color Theorem was true. Francis' brother, Frederick, was a student of De Morgan's at the time, when Francis told him about this problem. Shortly after Frederick revealed this conjecture to his mentor, DeMorgan, who was instantly intrigued by the problem. DeMorgan was so intrigued in fact he publicized it throughout the mathematical community, among the anouncements was the letter written to Hamilton from DeMorgan.

back to top.

Alfred Bray Kempe (1849-1922)

The Proofs...

One Mathematician was made very famous because of the Four Color Theorem, his name was Alfred Bray Kempe. Kempe was a barrister and a leading authority on ecclesiastical law. He studied mathematics at Cambridge University and maintained his interest for it through out his life. In his later years he devoted much time to mathematical research. Some of his contributions are in the area of motion, a form of mathematics known as kinematics, also he made contributions to mathematical logic. It seems odd then that he would have made such a famous "contribution" to mathematics through his fallacious proof of the Four Color Theorem ,which he published in 1979. Rosen says Kempe's proof was accepted for 11 years, and at the end of that 11 years, in 1890, Percy Heawood found the fatal error in the proof which made Kempe's argument incomplete.

The good news for Kempe, though he wasn't alive to hear it, was that his line of reasoning was used as the basis for American Mathematicians, Kenneth Appel and Wolfgang Haken's correct computer aided proof in 1976. They revealed that if the Four Color Theorem were false, there would have to be a counterexample in a set of approximately 2000 different types of counterexamples, and that none of these types actually exists. It took over 1000 hours of computer computation to carry out their proof. Because the proof was done with the aide of a computer, a lot of controversy floated to the surface. For example, was the computer, capable or did it, commit an error which could have led to fallacious results?

In 1996 Robertson, Sanders, Seymour, and Thomas reduced the computational part of the proof to examining 633 configurations thereby simplifying Appel and Haken's proof. Rosen believes that no other proof exists without this exstensive computation, but I am sure Dharwadker would argue.

Ashay Dharwadker proved the Four Color Theorem using group theory in 2000. Here is his outline of the proof:

back to top.

STEPS OF THE PROOF:

"We shall outline the strategy of the new proof given in this paper. In section I on MAP COLOURING, we define maps on the sphere and their proper colouring. For purposes of proper colouring it is equivalent to consider maps on the plane and furthermore, only maps which have exactly three edges meeting at each vertex. Lemma 1 proves the six colour theorem using Euler’s formula, showing that any map on the plane may be properly coloured by using at most six colours. We may then make the following basic definitions.

Define N to be the minimal number of colours required to properly colour any map from the class of all maps on the plane.
Based on the definition of N, select a specific map m(N) on the plane which requires no fewer than N colours to be properly coloured.
Based on the definition of the map m(N), select a proper colouring of the regions of the map m(N) using the N colours 0,1,…,N-1.

The whole proof works with the fixed number N, the fixed map m(N) and the fixed proper colouring of the regions of the map m(N). In section II we define STEINER SYSTEMS and prove Tits’ inequality and its consequence that if a Steiner system S(N+1,2N,6N) exists, then N cannot exceed 4. Now the goal is to demonstrate the existence of such a Steiner system. In section III we define EILENBERG MODULES. The regions of the map m(N) are partitioned into disjoint, nonempty equivalence classes 0,1,…, N-1 according to the colour they receive. This set is given the structure of the cyclic group Z_N={0,1,…, N-1} under addition modulo N. We regard Z_N as an Eilenberg module for the symmetric group S₃ on three letters and consider the split extension Z_N]S₃corresponding to the trivial representation of S₃. By section IV on HALL MATCHINGS we are able to choose a common system of coset representatives for the left and right cosets of S₃ in the full symmetric group on |Z_N]S₃| letters. For each such common representative and for each ordered pair of elements of S₃, in section V on RIEMANN SURFACES we establish a certain action of the two-element cyclic group on twelve copies of the partitioned map m(N) by using the twenty-fourth root function of the sheets of the complex plane. Using this action, section VI gives the details of the MAIN CONSTRUCTION. The 6N elements of Z_N]S₃ are regarded as the set of points and lemma 23 builds the blocks of 2N points with every set of N+1 points contained in a unique block. This constructs a Steiner system S(N+1,2N,6N) which implies by Tits’ inequality that N cannot exceed 4, completing the proof. The lemmas 1-23 and theorem 24 below are written in logical sequence."

The full proof is here:A NEW PROOF OF THE FOUR COLOR THEOREM: by Ashay Dharwadker

back to top.

References

Websites:

Dharwadker, A. (2000).A New Proof of The Four Color Theorem.

Retrieved April 29, 2005 from the World Wide Web:

http://www.geocities.com/dharwadker/main.html

Books:

Rosen K.H.(2003).Discrete Mathematics and Its Applications

(5th ed.).New York: McGraw-Hill.

Images:

Dharwadker, A.(2000).Figure 5.

Retrieved April 29, 2005 from the World Wide Web:

http://www.geocities.com/dharwadker/main.html

Rosen, K.H. (2003) DeMorgan Portrait, and Kempe Portrait.

Discrete Mathematics and Its Applications

(5th ed.).New York: McGraw-Hill.