On Graph Theory: The Coloring Problem

"Imagine a geographic map on the earth (that is, on a sphere) consisting of countries only - no oceans, lakes, rivers, or other bodies of water. The only rule is that a country must be a single contiguous mass - in one piece, and with no holes. As cartographers, we wish to color the map so that no two adjacent countries will be of the same color. How many colors should the map-maker keep in stock in order to be sure he/she can color any map?" (Francis W Guthrie, [question to his brother Frederick Guthrie], 1852)

"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 coloured so that figures with any portion of common boundary 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 five or more be invented." (De Morgan [letter to William R Hamilton], 1852)

"Some inkling of the nature of the difficulty of the question, unless its weak point be discovered and attacked, may be derived from the fact that a very small alteration in one part of a map may render it necessary to recolor it throughout. After a somewhat arduous search, I have succeeded, suddenly, as might be expected, in hitting upon the weak point, which proved an easy one to attack. The result is, that the experience of the map makers has not deceived them, the maps they had to deal with, viz.: those drawn on a [sphere] can in every case be painted with four colors." (Alfred Kempe," How to Colour a Map with Four Colours", The American Journal of Mathematics No. 1, 1879)

"The Descriptive-Geometry Theorem that any map whatsoever can have its divisions

properly distinguished by the use of but four colors, from its generality and intangibility, seems to have aroused a good deal of interest a few years ago when the rigorous proof of it appeared to be difficult if not impossible, though no case of failure could be found. The present article does not profess to give a proof of this original Theorem; in fact its aims are so far rather destructive than constructive, for it will be shown that there is a defect in the now apparently recognized proof [of Kempe’s]" (Percy J Heawood, 1890)

.

"It was terribly tedious, with no intellectual stimulation [...] There is no

simple elegant answer, and we had to make an absolutely horrendous case analysis

of every possibility. I hope it will encourage mathematicians to realize that there are

some problems still to be solved, where there is no simple God-given answer, and

which can only be solved by this kind of detailed work. Some people might think

they’re best left unsolved." (Kenneth Appel, [Times interview] 1976)

"Unfortunately, the proof by Appel and Haken (briefly, A&H) has not been fully accepted. There has remained a certain amount of doubt about its validity, basically for two reasons: (i) part of the A&H proof uses a computer, and cannot be verified by hand; (ii) even the part of the proof that is supposed to be checked by hand is extraordinarily complicated and tedious, and as far as we know, no one has made a complete independent check of it." (Paul Seymour, "A new proof of the four-colour theorem", Electronic Research Announcements of the American Mathematical Society 2, 1996)

"It is still the case that mathematicians are most familiar with, and most comfortable with, a traditional, self-contained proof that consists of a sequence of logical steps recorded on a piece of paper. We still hope that some day there will be such a proof of the four-color theorem. After all, it is only a traditional, Euclidean-style proof that offers the understanding, the insight, and the sense of completion that all scholars seek. For now we live with the computer-aided proof of the four-color theorem." (Steven G Krantz & Harold R Parks, "A Mathematical Odyssey: Journey from the Real to the Complex", 2014)

"One reason the four-color problem is challenging is that one cannot simply piece together colorings of smaller maps to get a desired coloring of a bigger map. [...] But if we try to put together two copies of the map side by side [...] then we will need to interchange some of the colors to avoid having a border with the same color on both sides. Similarly, if a new country is inserted somewhere in a four-colored map, then some of the existing colors may need to be changed to color the new map with only four colors." (Steven G Krantz & Harold R Parks, "A Mathematical Odyssey: Journey from the Real to the Complex", 2014)

"Bertrand Russell has said that ’mathematics is the subject in which we never knowwhat we are talking about nor whether what we are saying is true.' Unfortunately, the purely formal view is difficult to uphold, paradoxically for formal reasons. We know the difficulties presented by the formalization of arithmetic associated with Gödel’s Theorem. [...] For myself, I am content with the following illustration: Let us suppose that we have been able to construct for a formal theory S an electronic machine M capable of carrying out at a terrifying speed all the elementary steps in S. We wish to verify the correctness of one formula F of the theory. After a process totaling 1030 elementary operations, completed in a few seconds, the machine M gives us a  positive reply. Now what mathematician would accept without hesitation the validity of such a ‘proof,’ given the impossibility of verifying all its steps?" (René Thom, The American Scientist)