crummer%AEROSPACE@sri-unix.UUCP (02/02/84)
From: Charlie Crummer <crummer@AEROSPACE> Fortunately (or unfortunately) puzzles like Fermat's Last Theorem, Goldbach's conjecture, the 4-color theorem, and others are not in the same class as the geometric trisection of an angle or the squaring of a circle. The former class may be undecidable propositions (a la Goedel) and the latter are merely impossible. Since one of the annoying things about undecidable propositions is that it cannot be decided whether or not they are decidable, (Where are you, Doug Hofstader, now that we need you?) people seriously interested in these candidates for undecidablilty should not dismiss so-called theorem provers like A. Arnold without looking at their work. I have heard that the ugly computer proof(?) of the 4-color theorem that appeared in Scientific American is incorrect, i.e. not a proof. I also have heard that one G. Spencer-Brown has proved the 4-color theorem. I do not know whether either of these things is true and it's bugging me! Is the 4-color theorem undecidable or not? --Charlie
ags@pucc-i (Seaman) (02/07/84)
> I have heard that the ugly computer proof(?) of the 4-color theorem that > appeared in Scientific American is incorrect, i.e. not a proof. I also > have heard that one G. Spencer-Brown has proved the 4-color theorem. I > do not know whether either of these things is true and it's bugging me! > Is the 4-color theorem undecidable or not? > > --Charlie I don't believe the proof has appeared in S.A. -- only a description of the method that was used to generate the proof. The proof itself is a length computer listing and does not make interesting reading. Martin Gardner's column once contained (in an April issue) a claim that the problem had been solved. A map was reproduced that supposedly required five colors. This was before the computer proof was announced. -- Dave Seaman ..!pur-ee!pucc-i:ags "Against people who give vent to their loquacity by extraneous bombastic circumlocution."
simon@psuvax.UUCP (02/08/84)
There is no graph, published in Scientific American or elsewhere, that is planar and requires five colors. There were examples of graphs (I believe there was one published in SA) for which simplistic 4-coloring strategies failed. The proof is more than a computer listing: it consists of a strategy for "discharging" (not original to Haken & Appel), together with a recursive proof that any graph, after suitable discharging, is four-colorable iff a certain set of irreducble graphs is. The computer was used both to help with vrifying all cases of this proposition, and getting 4-colorings for the 1500 or so irreducible ones. The computer program ran for a long time: it has never been formally certified to be correct. js
sher@rochester.UUCP (David Sher) (02/09/84)
The interesting part of the proof of the 4 color theorem was the proof that
you need only check it for a finite set of special cases. This was proved
some time ago. (I think, I'm not a graph theorist so am not authoritative)
If you believe this then the 4 color theorem is definitely decidable. You
may dispute the efficacy of this particular proof technique.
-David Sher (ofttimes AI project) {he's back}
sher@rochester
seismo!rochester!shersegre@uicsl.UUCP (02/12/84)
#R:sri-arpa:-1640300:uicsl:15500024:000:662 uicsl!segre Feb 10 10:12:00 1984 The four color conjecture of (Guthrie 1852), "Every planar graph is four-colourable," was proved correct by Appel and Haken at the University of Illinois. This is the "ugly" computer proof you refer to. [Bull. Amer. Math. Soc., 82]. This proof is considered correct - claims to "ugliness" are due to the method used which required large amounts of computer time to prove four-colourability of an exhaustive set of subgraphs. There is nothing "ugly" about the method, except that before the availability of computers it wouldn't have been possible to use such a method. As of today there is no other proof that I know of. Alberto Segre ...uiucdcs!uicsl!segre
darrelj@sdcrdcf.UUCP (Darrel VanBuer) (02/13/84)
Martin Gardner published a (purported) 5-color graph in his column
in Scientific American in April of a year around 1974 (I'm sure of April,
due to contents of the column fitting the first day). This column contained
about a dozen interesting "results" in mathematics, none of them true! but
many of them quite convincing, almost all of them difficult to verify. As I
recall, the last few were pretty hokey sounding, but the first half could
have fooled almost anybody.
--
Darrel J. Van Buer, PhD
System Development Corp.
2500 Colorado Ave
Santa Monica, CA 90406
(213)820-4111 x5449
...{allegra,burdvax,cbosgd,hplabs,ihnp4,sdccsu3,trw-unix}!sdcrdcf!darrelj
VANBUER@USC-ECL.ARPAags@pucc-i (Seaman) (02/14/84)
> There is no graph, published in Scientific American or elsewhere, that is > planar and requires five colors. I never said there was. What I said was that Martin Gardner's column once contained (in an April issue) a graph which PURPORTEDLY required five colors. I did not think it would be necessary to point out to readers of this newsgroup that the graph was an April Fool Joke. Martin Gardner himself explained how to color it (with 4 colors) in a later column. -- Dave Seaman ..!pur-ee!pucc-i:ags "Against people who give vent to their loquacity by extraneous bombastic circumlocution."