Four Colors Suffice : How the Map Problem Was Solved

Rating:
Summary: When is a proof a proof?
Review: 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).

Rating:
Summary: Mathematical Teamwork, And The Philosophy of Proof
Review: 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.

Rating:
Summary: Interesting and Informative
Review: 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.

Rating:
Summary: A tale of many great features of mathematics
Review: 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.

Rating:
Summary: If you like mathematics you'll like this!
Review: This book deserves every star it gets from me! The quality of the writing startled me since afterall it was written by a mathematician. The four color problem was presented in a fascinating manner. Brief histories on the people who worked on the problem were very interesting and added flavor. Also, the book was not dry. It had nice anecdotes and a sense of humor ("humour"-see below). Diagrams and formulas were presented in a very clear concise manner to anyone who has a good geometrical foundation or higher.
My nitpicky thoughts that would probably never bother anyone else:
The title is deceptive. "Colors" is spelled "colour" in the actual text.
Also, the example of the shape of football was used in the text. What he meant was a soccerball. Completely different shapes come to mind.
My last nitpicky thing is on the same British/American culture line of reasoning. Apparently the Brit's use a term called "overleaf" I finally realized that he meant "on the next page" about half way through. Other than the regional differences in language, the work was presented beautifully. I plan on looking for anything else Mr. Wilson has written. I've always loved math but never really liked reading about it. This book has definitely sparked an interest in reading more like this!

Rating:
Summary: If you like mathematics you'll like this!
Review: This book deserves every star it gets from me! The quality of the writing startled me since afterall it was written by a mathematician. The four color problem was presented in a fascinating manner. Brief histories on the people who worked on the problem were very interesting and added flavor. Also, the book was not dry. It had nice anecdotes and a sense of humor ("humour"-see below). Diagrams and formulas were presented in a very clear concise manner to anyone who has a good geometrical foundation or higher.
My nitpicky thoughts that would probably never bother anyone else:
The title is deceptive. "Colors" is spelled "colour" in the actual text.
Also, the example of the shape of football was used in the text. What he meant was a soccerball. Completely different shapes come to mind.
My last nitpicky thing is on the same British/American culture line of reasoning. Apparently the Brit's use a term called "overleaf" I finally realized that he meant "on the next page" about half way through. Other than the regional differences in language, the work was presented beautifully. I plan on looking for anything else Mr. Wilson has written. I've always loved math but never really liked reading about it. This book has definitely sparked an interest in reading more like this!