ISBN-10:
0691120234
ISBN-13:
9780691120232
Pub. Date:
11/07/2004
Publisher:
Princeton University Press
Four Colors Suffice: How the Map Problem Was Solved

Four Colors Suffice: How the Map Problem Was Solved

by Robin Wilson

Paperback

Current price is , Original price is $27.95. You
Select a Purchase Option (New Edition)
  • purchase options

Product Details

ISBN-13: 9780691120232
Publisher: Princeton University Press
Publication date: 11/07/2004
Edition description: New Edition
Pages: 280
Product dimensions: 5.50(w) x 8.00(h) x (d)

About the Author

Robin Wilson is Head of the Pure Mathematics Department at the Open University and Fellow of Keble College, Oxford University. He is Gresham Professor of Geometry at Gresham College, London, and is a frequent visitor to Colorado College. He has written and edited about 25 books on topics ranging from graph theory via philately, to the Gilbert and Sullivan operas, to the history of mathematics.

Read an Excerpt

Four Colors Suffice

How the Map Problem Was Solved
By Robin Wilson

Princeton University Press

Copyright © 2003 Princeton University Press
All right reserved.

ISBN: 0-691-11533-8


Chapter One

The four-colour problem

Before we embark upon our historical journey, there are a number of basic questions to be answered. First and foremost, of course, is this:

What is the four-colour problem?

The four-colour problem is very simply stated, and has to do with the colouring of maps. Naturally, when colouring a map we wish to colour neighbouring countries differently so that we can tell them apart. So how many colours do we need to colour the entire map?

At first sight it seems likely that the more complicated the map, the more colours will be required - but surprisingly this is not so. It seems that at most four colours are needed to colour any map - for example, in the map of Britain shown opposite, the counties have been coloured with just four colours. This, then, is the four-colour problem:

Four-colour problem

Can every map be coloured with at most four colours in such a way that neighbouring countries are coloured differently?

Why is it interesting?

Solving any type of puzzle, such as a jigsaw or crossword puzzle, can be enjoyed purely for relaxation and recreation, and certainly the four-colour problem has provided many hours of enjoyment - and frustration - for many people. At another level, the four-colour problem can be regarded as a challenge. Just as climbing a mountain can present a climber with major physical obstacles to overcome, so this problem - so simple to state, yet apparently so hard to solve - presents mathematicians with an intellectual challenge of enormous complexity.

Is it important?

Rather surprisingly, perhaps, the four-colour problem has been of little importance for mapmakers and cartographers. In an article on the problem's origin written in 1965, the mathematical historian Kenneth May observed:

A sample of atlases in the large collection of the Library of Congress indicates no tendency to minimize the number of colors used. Maps utilizing only four colours are rare, and those that do usually require only three. Books on cartography and the history of mapmaking do not mention the four-color property, though they often discuss various other problems relating to the coloring of maps ...

The four-color conjecture cannot claim either origin or application in cartography.

Equally, there seems to have been no interest shown by quilt-makers, patchworkers, mosaicists and others in restricting the number of colours of patches or tiles to four.

However, the four-colour problem is more than just a curiosity. In spite of its recreational nature, the various attempts to solve it over the years have stimulated the development of much exciting mathematics with many practical applications to important real-world problems. Many practical network problems - on road and rail networks, for example, or communication networks - derive ultimately from map-colouring problems. Indeed, according to a recent book in the related area of graph theory (the study of connections between objects), the entire development of the subject can be traced back to attempts to solve the four-colour problem. In the theory of computing, recent investigations into algorithms (step-by-step procedures for solving problems) are similarly linked to colouring problems. The four-colour problem itself may not be part of the mathematical mainstream, but the advances it has inspired are playing an increasingly important role in the evolution of mathematics.

What is meant by 'solving' it?

To 'prove the four-colour theorem' is to show that four colours are sufficient to colour all maps - be they geographical maps of the world, or fictitious ones we may care to invent. If its statement were false, we would have to demonstrate the fact by presenting a map that requires five colours or more - just a single map will do. But if the statement is true, then we must prove it for all possible maps: it is not enough to colour millions or even billions of maps, because there may still be a map that we have missed whose arrangement of countries requires five or more colours. In other areas of science, proofs assert that a given hypothesis is overwhelmingly likely given the underlying assumptions and the experiments that have been carried out, but a mathematical proof has to be absolute - no exceptions are allowed. To prove the four-colour theorem we must find a general argument that applies to all maps, and discovering such an argument turns out to require the development of a great deal of theoretical machinery.

Who posed it, and how was it solved?

As we shall see, the four-colour problem was first posed by Francis Guthrie around a hundred and fifty years ago, but more than a century of colouring maps and developing the necessary theoretical machinery would pass before it was established with certainty that four colours suffice for all maps. Even then, difficult philosophical questions have remained. The eventual solution, by Wolfgang Haken and Kenneth Appel in 1976, required over a thousand hours of computer time, and was greeted with enthusiasm but also with dismay. In particular, mathematicians continue to argue about whether a problem can be considered solved if its solution cannot be checked directly by hand.

PAINTING BY NUMBERS

Before we begin our historical narrative, we need to explain more clearly what the four-colour problem is, and what our underlying assumptions are. For example, what do we mean by a 'map'?

We may think of a map as consisting of a number of countries or regions. These may be counties if part of a British map, or states if part of a map of the USA. The boundary of each country is made up of several boundary lines, and these boundary lines intersect at various meeting points. Two countries with a boundary line in common are called neighbouring countries - for example, in the following map the countries A and B are neighbouring countries.

When colouring a map we must always give neighbouring countries different colours. Notice that some maps do need four colours: map (a) below has four mutually neighbouring countries, each meeting the other three; these countries must all be coloured differently, so four colours are required. This can happen in practice: in map (b), Belgium, France, Germany and Luxembourg are all neighbouring countries, so the map requires four colours.

Some maps do not need four colours. For example, in each of the following maps, the outer ring of countries can be coloured with two colours (red and green) that alternate as we proceed around the ring; the country in the centre must be then assigned another colour (blue), so that just three colours are required.

Notice that four colours may be needed even when the map does not contain four mutually neighbouring countries. In the map below, the outer ring of five countries cannot be coloured with two alternating colours, and so requires a third colour. The country in the centre must then be coloured differently from these three, so four colours are required.

This last situation also arises when we colour the 48 contiguous states of the USA (excluding Alaska and Hawaii). Here, the western state of Nevada is surrounded by a ring of five states, Oregon, Idaho, Utah, Arizona and California: this ring of states requires three colours, and Nevada must then be assigned a fourth colour. This colouring with four colours can then be extended to the entire map, as shown opposite.

We can make a couple of further observations about this map. Notice first that at one point of the United States four states meet - Utah, Colorado, New Mexico and Arizona. We shall adopt the convention that when two countries meet at a single point, we are allowed to colour them the same - so Utah and New Mexico may be coloured the same, as may Colorado and Arizona. This convention is necessary, since otherwise we could construct 'pie maps' that require as many colours as we choose - for example, the eight-slice pie map below would need eight colours, since all eight slices meet at the centre. With our convention, this map requires only two colours.

Another familiar 'map' that needs only two colours is the chessboard. At each meeting point of four squares we alternate the colours black and white, producing the usual chessboard colouring (see over).

The other feature of the United States map we need to note is that the state of Michigan is in two parts (separated by one of the Great Lakes) that must be assigned the same colour. Although a divided country or state may cause no difficulty in particular situations, such as in the map of the United States, consider the following map in which the two regions numbered 1 are to be regarded as parts of the same country. Here, each of the five 'countries' has a boundary line in common with the other four, so five colours are required:

From now on, we avoid such undesirable situations by requiring that each country must be in one piece.

Some people also like to include the 'exterior region' in their colourings. Generally speaking, it is immaterial whether we do so or not, since we can regard this exterior region as an extra (ring-shaped) country (see opposite, top).

However, a more useful way of thinking about the exterior region is to consider the map as drawn on a globe, rather than on the plane. In this case, the exterior region appears as no different from any other region.

In fact, drawing maps on the plane is equivalent to drawing maps on a globe or, in the language of mathematics, on the surface of a sphere. We can see this from the following illustration, which depicts what is termed a stereographic projection, from the sphere onto the plane on which it rests. Starting with any map on the sphere, we can project it down from the North Pole to give us a map on the plane. Conversely, given any map on the plane, we can project it up onto the sphere.

Notice that these projections do not affect the colouring of the map - if two neighbouring countries are coloured red and green, then after projection (in either direction) their images will also be red and green. It follows that we can restate the four-colour problem as a problem about the colouring of maps on a sphere:

Four-colour problem for a sphere

Can every map drawn on the surface of a sphere be coloured with at most four colours in such a way that neighbouring countries are coloured differently?

If we can solve the four-colour problem for maps drawn on a sphere, then we immediately obtain a solution for maps drawn on the plane. Conversely, if we can solve the four-colour problem for maps drawn on the plane, then we immediately obtain a solution for maps drawn on a sphere. So it makes no difference whether we think of our maps as drawn on the plane or on the surface of a sphere and so, for each map, we can choose whether or not to colour the exterior region.

There are some further simplifications which do not materially affect the four-colour problem itself, but which will help to simplify our explanation. It almost goes without saying that every map we consider is in one piece, since we could treat the various pieces as maps in their own right and colour them all separately. Similarly, we can rule out any map that consists of pieces joined together at a single point, since again we could colour the various pieces separately: in particular, we can ignore countries with a single boundary line. Thus, we can ignore any maps like these:

Finally, we can assume that there are at least three boundary lines at each meeting point. If there were only two boundary lines at a meeting point, then we could simply remove the point without affecting the colouring.

In fact, as we shall see in Chapter 4, when trying to solve the four-colour problem we can always restrict our attention to maps where there are exactly three boundary lines at each meeting point, as in the map overleaf. Such maps are very common, and we give them a special name: we call them cubic maps. You might like to try to colour this map with four colours. (Can it be coloured with just three?)

TWO EXAMPLES

To end this chapter, here are two practice problems about the colouring of maps on the plane.

Example 1

In the following map, three countries have already been assigned colours. How can we colour the entire map with the four colours red, blue, green and yellow?

Notice first that country A has a boundary line in common with countries coloured green and yellow, and so must be coloured either blue or red. Let us look at each of these possibilities in turn.

If country A is coloured blue, then F must be coloured red (since it shares a boundary line with countries coloured blue, green and yellow). Country D must then be coloured green, and E must be coloured yellow. This gives the following colouring.

But it is now impossible to colour country ITLITL, since it has boundary lines in common with countries of all four colours. So A cannot be coloured blue, and must be coloured red.

Country F must now be coloured blue, C must be coloured green, D red, and E yellow. We must then colour country H red, G green, B yellow, I green and J blue. This completes the colouring.

Example 2

Our second example first appeared as an April Fool's joke! For several years Martin Gardner wrote a highly successful mathematical column in the pages of Scientific American, and many of his columns were later collected in book form. In the 1 April 1975 issue of the magazine he decided to play a trick on his readers by presenting 'Six sensational discoveries that somehow or another have escaped public attention'. They included a chess-playing machine (then considered impossible), a thought experiment that disproved Einstein's theory of special relativity, and the discovery of an ancient manuscript establishing Leonardo da Vinci as the first inventor of the valve flush toilet. The column declared:

The most sensational of last year's discoveries in pure mathematics was surely the finding of a counterexample to the notorious four-color-map conjecture ... Last November, William McGregor, a graph theorist of Wappingers Falls, N.Y., constructed a map of 110 regions that cannot be colored with fewer than five colors.

Continues...


Excerpted from Four Colors Suffice by Robin Wilson Copyright © 2003 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Table of Contents

Prefacexi
1The four-colour problem1
What is the Four-colour Problem?
Why Is It Interesting?
Is It Important?
What Is Meant by 'Solving' It?
Who Posed It, and How Was It Solved?
Painting by Numbers
Two Examples
2The problem is posed16
De Morgan Writes a Letter
Hotspur and the Athenaeum
Mobius and the Five Princes
Confusion Reigns
3Euler's famous formula38
Euler Writes a letter
From Polyhedra to Maps
Only Five Neighbours
A Counting Formula
4Cayley revives the problem ...60
Cayley's Query
Knocking Down Dominoes
Minimal Criminals
The Six-Colour Theorem
5... and Kempe solves it73
Sylvester's New Journal
Kempe's Paper
Kempe Chains
Some Variations
Back to Baltimore
6A chapter of accidents95
A Challenge for the Bishop
A Visit to Scotland
Cycling Around Polyhedra
A Voyage Around the World
Wee Planetoids
7A bombshell from Durham116
Heawood's Map
A Salvage Operation
Colouring Empires
Maps on Doughnuts
Picking Up the Pieces
8Crossing the Atlantic143
Two Fundamental Ideas
Finding Unavoidable Sets
Finding Reducible Configurations
Colouring Diamonds
How Many Ways?
9A new dawn breaks169
Doughnuts and Traffic Cops
Heinrich Heesch
Wolfgang Haken
Enter the Computer
Colouring Horseshoes
10Success!...190
A Heesch-Haken Partnership?
Kenneth Appel
Getting Down to Business
The Final Onslaught
A Race Against Time
Aftermath
11... but is it a proof?214
Cool Reaction
What is a Proof Today?
Meanwhile ...
A New Proof
The Future ...
Notes and references229
Chronology of events245
Glossary249
Picture credits255
Index257

What People are Saying About This

Kenneth Appel

Robin Wilson has combined a complete history of the approach that led to the solution of the four color problem with a description of the techniques involved that can be read with pleasure and comprehension by undergraduates as well as professional mathematicians.
Kenneth Appel, University of New Hampshire

Ian Stewart

An intriguing historical account of one of the most baffling enigmas in mathematics: the Four Color Theorem. Robin Wilson provides fascinating insights into how mathematicians think, and shows that questions that are simple to ask may not be simple to answer.

John Conway

I loved Robin Wilson's book on the four color problem, because it gives the history as well as the arguments. The history is presented so entertainingly, and the arguments so lucidly, that I'm sure the book will find a large audience, and delight any audience as much as it did me.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews

Four Colors Suffice: How the Map Problem Was Solved 4 out of 5 based on 0 ratings. 2 reviews.
LMHTWB on LibraryThing 22 days ago
The title Four Colors Suffice refers to a simple mathematics problem that was first discussed in the 1850's. Namely, how many colors does it take to color a map so that no two bordering countries have the same color? The answer appeared to be 4 colors, but proving that took 150 years and required the use of computers. This book traces the history of the problem from the first publications to the proof of it in 1976, plus a discussion of the validity of a computer proof.The writing overall was fine -- not brilliant, not poor, but somewhere in the middle. For some of the mathematics, the discussion was a bit unclear and hard to follow. (Yes, the methods used by various attempted proofs are difficult topics, but even having a decent mathematical background, I had to reread several pages to understand what he was trying to say.) The diagrams were terrific! The history was well researched with notes and a bibliography.On the down side, the book lacked somewhat. As mentioned above, some areas were obtuse. Also some topics, such as why this is an important problem and not just a "let's see if we can prove it" type of problem, were alluded to but never really discussed. Wilson stated several places that the math used to solve this problem led to other important results, such as...well, he never says. Also, the final section as to whether or not the proof is valid felt like it was added later, without much enthusiasm. Proof by exhaustive computer search is a very interesting question -- is it really a proof? I understand that a thorough discussion would involve a lot of discussion of computer programming, but this book (as evidenced by the level of math when discussing the historic proofs) is aimed for a mathematical literate audience that could understand the basics of the computer issues.Overall, the history part of the book was fine, but the "we have a proof" section was lacking. I will probably read it again at sometime, but not terribly soon.
_Zoe_ on LibraryThing 22 days ago
I don't know why this book has so many low ratings; they're entirely undeserved. Wilson makes clear the important conceptual issues without going into too much minute detail, and does it in a way that's thoroughly entertaining to read. The book strikes a good balance between humorous anecdotes and serious mathematics. If you don't have any interest in math, you obviously shouldn't bother with this book. On the other hand, if you're looking for a textbook, this isn't it--and it's not supposed to be.