Customer Reviews

Four Colors Suffice: How the Map Problem Was Solved

5 star:		(4)
4 star:		(4)
3 star:		(0)
2 star:		(0)
1 star:		(1)

 

 

One of the most famous theorems in mathematics is the Four Color Map Theorem. It is wonderfully simple to understand, and interesting to spend time doodling on. Mapmakers like to take a map like, say, the states of the U.S. and color in the states with different colors so they are easily told apart; the theorem states that any such map (or any imaginary map of contiguous regions), no matter how complex, only requires four colors so that no state touches a state of the same color. This is not obvious, but if you try to draw blobs on a sheet of paper that need more than four colors (in other words, five blobs each of which touches all the others along a boundary), you will quickly see that the theorem seems to be true. In fact, ever since the question was mentioned, first in 1852, people have tried to draw maps that needed five colors, many of them very complicated, but no one succeeded. But that isn't good enough for mathematics; it's interesting that no one could do it, but can it be proved that it cannot be done? For over a century, there was no counter-example and yet no proof, but in 1976 there was a proof that has held up, but is controversial because it used a computer. The amazing story of the years of competition and cooperation that finally proved the theorem is told in _Four Colors Suffice: How the Map Problem Was Solved_ (Princeton) by Robin Wilson. This is as clear an explanation of the problem, and the attempts to solve it, as non-mathematicians are going to get, and best of all, it is an account, exciting at times, of the triumphs and frustrations along the way, not just with the final proof, but in all the years leading up to it.

Surprisingly, mapmakers aren't very interested in the problem. It was first mentioned in writing in 1852, and in 1879, Alfred Kempe published one of the most famous proofs in mathematics, famous because it proved the theorem and famous because, although it was accepted for about a decade, it was wrong. Kempe's work was useful, as it was an attack on the problem that others eventually used in different ways, but it did not stand. Percy Heawood published a paper in which he included a diagram that Kempe's method could be used on and for which Kempe's method failed. (Not that more than four colors were needed for the map; it simply showed Kempe's method didn't cover all possibilities.) Heawood built on Kempe's work to prove a five color map theorem, but the four color version proved elusive. There was so much data developed in proofs in the 1960s that computers became essential to handle them. Wolfgang Haken worked on the theorem, and was told by computer experts that his ideas could not be programmed, but programmer Kenneth Appel disagreed. In 1972, Haken and Appel teamed up to work on a computer-aided solution, and in 1976, they announced it. They were rushing, as other map-colorers were coming close to a solution themselves. The proof required a thousand hours of computer time, a hundred pages of summary, a hundred pages of detail, and seven hundred pages of back-up work. The computer printouts for it stacked to four feet high. The long hunt was over, but it was not satisfactory to everyone. The problem is that the computer did so much work on the proof that humans cannot check everything the computer did; some mathematicians, especially older ones, have not accepted this proof, although no significant error has been found.

_Four Colors Suffice_ not only explains the theorem and historic attempts at proofs in a clear fashion, it is an inspiring look at something that is really rather lovable in our species, the pursuit of mathematical knowledge for its own sake. To be sure, the theorem does have practical interest, if not to actual mapmakers, then to road, rail, and communications networks, but it has mainly inspired other aspects of pure mathematics like graph theory and algorithms. There are many stories of cooperation between mathematicians here that make the final conquest of the problem seem like a team effort that has been conducted for over a century. One example: when Haken and Appel needed referees to check their paper, one of them was a mathematician who was bitterly disappointed that his own proof had not scooped them. His work as a referee proved to be conscientious and constructive. This may be a tale of a proof that only a computer could crack, but it is a handsome human success story.

Review of: "Four Colors Suffice - How the Map Problem Was Solved"

By: Robin Wilson

The four color map theorem is easy to understand and hard to prove.

The four color map theorem states that on a plane, which is divided into non-overlapping contiguous regions, the regions can be colored with four colors in such a way that all regions are colored and no two adjacent regions have the same color. In other words you can color any ordinary map with just four colors.

The proof of the four color theorem is very difficult. It is so difficult that the proof took over a century. The search for a proof was so long and became so complex that some mathematicians speculated that it was impossible. The four color served as one of the first real mathematical challenges posed to mathematics undergraduate students.

The statement of the challenge was deceptively simple. Prove that four colors are sufficient. The statement of the problem is so simple that it seems the solution should be equally simple. It is not simple. In 1976 the four-color theorem was finally demonstrated. The authors of the proof are Kenneth Appel and Wolfgang Haken of the University of Illinois.

The book "Four Colors Suffice" is the story of the century long search for the proof. The effort culminated in a computer program. Appel and Haken restated the problem as a collection of 1,936 types of maps. They had a computer program prove each of these 1,936 forms.

The author succeeds in conveying the excitement of the competition in those final months. This book shows the drama of one of the most exciting episodes of modern mathematics.

See also:

Graphs, Colourings and the Four-Colour Theorem (Oxford Science Publications)

The Four-Color Theorem: History, Topological Foundations, and Idea of Proof

Introduction to Graph Theory (4th Edition)

I thoroughly enjoyed this thoughtful and exciting book.

I am a mathematician extensively familiar with the Four-Color Theorem and I was impressed by Wilson's book. He knows just what to put in and what to leave out; the narrative has just the right mixture of storytelling and math. If I have one complaint it is that the discharging procedure (part of the proof) is rather glanced over, but I can see how it would be daunting to expose "real" discharging procedures to a non-mathematical audience.

Overall, an entertaining and elegant book.

Four Colors Suffice explains the history and some of the mathematics behind the four color theorem. While it goes into depth about it's history, there are chatty stories about the mathematicians, the book does not go into great depth about the mathematics involved. There are some mathematics, though, even some proofs. I consider this a good introduction to the four color theorem but it left me wanting more. I recommend this book for the story behind the four color theorem and also for a light introduction to the math but look elsewhere for an in depth discussion of the math.

Saw this in the bookshop the other week and bought it on impulse. Surprisingly (to me anyway) I was not even aware that the Four Colour theorem had been proven. This book does an excellent job of presenting the history of the theorem, early attempts to solve it, its ultimate proof and the reaction of the maths world to this proof. Along the way you get a solid grounding in the basics of the theorem and how the final proof evolved.

I found the book interesting and informative. Generally the maths is pretty straight forward but there are times when you'll need to think carefully about graphs and lines joining points in the plane. I found I had to reread some earlier sections as you need to understand the basics as you proceed through to the final proof. Probably not a book for anyone who is not prepared to put some mental work into it.

Obviously four stars for this book - each of a different colour.

The history of the four color problem is one that illuminates much of what makes mathematics such a great topic to explore and was the first instance of a whole new movement in mathematics. It started with a letter from Augustus De Morgan in 1852, where he asks a question that was first asked of him by a student.

"What is the least possible number of colors needed to fill in any map (real or invented) so that neighboring countries are always colored differently?"

This apparently simple question was not immediately resolved, and over the years there were many attempts to answer it. In 1879, Alfred Bray Kempe published what was thought to be a proof that four colors were enough, but it turned out that the proof was flawed. It was only when the problem was reduced to a set of special cases that could be examined by a computer that a conclusive "proof" was finally derived by a computer in 1976. Kenneth Appel and Wolfgang Haken, who have been given credit for resolving the problem, programmed the computer. Many mathematicians found this type of proof very unnerving, and it forced the mathematical community to reexamine what the definition of a mathematical proof really is.
This story, told very well by Robin Wilson, has student input, progress that proceeds in fits and starts with one major false proof, reduction of the problem to simpler terms based on new ideas and different approaches to the problem and the unprecedented proof of a major result by computer analysis. It also demonstrates how persistent the mathematical community can be when confronted with an unsolved problem. As befits the topics, Wilson relies heavily on diagrams to get his points across, which is a necessity. Like the statement of the problem, the diagrams are easy to understand and they alter it so that it is more in the nature of a puzzle than a mathematical problem.
I enjoyed this book immensely, both as a historical account of what is right about mathematics and as a description of a persistent process that leads to truth. This book would make an excellent text for history of mathematics courses.

Published in the recreational mathematics e-mail newsletter, reprinted with permission.

It's one of those great problems in math: easy for anyone to understand, baffling on the complexities of its solution, and unsolved for over a century. The question is: If you want to color a map so that countries with shared borders are different colors, how many colors do you need? What's the smallest number? A four year old can understand the question, but it took a fundamental revolution in mathematical proofs to state the answer with certainty: Four colors suffice.

This is a very readable history of the problem, from its phrasing in the mid-nineteenth century up to its mind-boggling proof in 1976, and a bit beyond that. It captures brief bits of the lives of the mathematicians who worked on it, as well as the furor over Appel and Haken's computer-based proof. Why was this so revolutionary? Because it was the first proof with steps that could never be checked by a human reader. Some people claimed the proof was incomplete until the programs were proven correct. Others stated that, if it couldn't be proven to a human mind, then nothing was really proven at all. Yet others objected to the proof's lack of mathematical elegance. It wasn't a scalpel that cut neatly to the heart of the problem, but a bulldozer hauled away huge buckets of potential counterexamples. A non-mathematician like me has to wonder: did this pave the way for acceptance of the 15,000-page "Classification theorem"? Although that theorem might not have been proven with computer assistance, its sheer mass is certainly similar.

The book does get a bit mathematical in places. The casual (and maybe not-so-casual) reader will be tempted to skip bits, and won't really lose the narrative thread by doing so. And, since the original proof is nearly 30 years old now, some of the excitement has worn off it. Even so, it's an enjoyable history of a problem that resisted attack for so long, and the remarkable attack that finally felled it.

And it leave me wondering: do my younger colleagues live in a world richer because of the radical solution, or poorer for the absence of such a wonderful mystery?

//wiredweird

I enjoyed this book very much - it is fresh in expression and introducing complex ideas - even humourous at times! And yet for all that there is a sense of some lack of achievement also, although this may not be a failing of Mr Wilson.

As a mathematics student - and I have studied quite a lot of mathematics - it seems to me that proofs came in three kinds. There are the mind opening 'obvious' ones that are so stand-alone that once you read them there is nothing to learn. The blinkers have been lifted from the eyes and the world is a different place. Then there are the proofs that take such a lot of work to assimilate and for a long time you just don't see it. Perhaps you never really do, but you do come to accept it because the mathematics community is convinced. Then there are the proofs that even the mathematics community struggle with. The four-colour problem's proof is one of these. Consequently there is left a nagging doubt, which I gather is quite widespread amongst people far wiser and knowledgeable than me - than Mr Wilson also I suspect.

The curious thing is that a conjecture like the four-colour mapping, or Fermat's last theorem, or the conjecture that all even numbers can be made up of the sum of two prime numbers, is so powerful AND there are no counter examples available to challenge the conjecture. So why can they not be proved by some elegant insight such as Fermat claimed for his last theorem but never showed the world before his immanent death in a duel? Why can the four-colour problem only be proved by such inelegant computer-assisted means as this book describes? Perhaps Mr Wilson's greatest achievement is in exposing the doubts and dissatisfactions of the current proof of the four-colour problem despite the appearance that it may well be adequate (this goes for the proof of Fermat's last theorem too).

This book was dissapointing. Clearly, it was just the year's general audience math book that publishers decided to put their money behind. I am not a mathematician, but I do have a good grasp of and enjoyment for mathematics. I have also always been interested in this problem, so I was excited when I found this book in the book store. However, the author is a fairly bad writer, and not as accomplished as he could be explaining ideas to a general audience (although he is not terrible at this either). More damning, is that the topic is not really that interesting in the end, the proof does not say too much interesting about shapes or geometries. The author admits at the beginning that the theorem has not been too useful for other applications, and it has not inspired too much. In working towards a proof math discoveries were made, and the debate over whether it is a prood were really the only useful parts of the journey towards a proof.

Theauthor puts in every tangential, mildly interesting anecdote to keep the book readalbe. While, certainly, this type of thing can work, here it is obviously just filler, with the author getting a kick out of these mildly amusing stories. I wouldn't recommend this book.