Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


quasi
Posts:
12,042
Registered:
7/15/05


Re: A Simple Proof of The Four Color Theorem
Posted:
Jul 2, 2013 9:23 PM


bill wrote: >quasi wrote: >>bill wrote: >>> >>>Kempe's method was accepted as proof of the FCT until >>>Heawood created his counterexample. >>> >>>Suppose that there was a simple way to 4color Heawood's graph >>>>without worrying about the problem of "tangled chains"? Would >>>that be sufficient for a proof? >> >> No. >> >> Heawood's graph is a counterexample to Kempe's proposed coloring >> strategy. According to Kempe's claimed proof, Heawood's graph can >> be 4colored by a specific strategy used in the proof. Heawood >> identifies a specific planar graph which, if one follows Kempe's >> coloring strategy, then two adjacent vertices will be forced to >> have the same color. The result is to show that Kempe's proof is >> invalid as a proof of 4colorability for planar graphs. >> >If Kempe's strategy had been applied to the coloriing with the >two adjacent vertices with the same color; it would have been >successful.
Heawood was just following the coloring strategy which, based on the supposedly proved claims in Kempe's proof, _had_ to work. The fact that it didn't work invalidates Kempe's claim, and with it, the whole proof.
If Kempe could have fixed the proof by reworking his coloring strategy, he surely would have done so.
The fact that Heawood's graph _can_ be 4colored doesn't resolve the dilemma. Heawood's graph is just one counterexample to Kempe's proposed coloring  one out of infinitely many. If you could somehow show (in a simple way) that _all_ possible counterexamples to Kempe's coloring strategy are 4colorable, that would achieve your goal of producing a simple proof of the 4CT.
>Why do we expect Kempe's strategy to succeed on the first trial >when no other method is under the same restrictions?
Because Kempe's proof claimed that his coloring strategy would _always_ produce a 4coloring. Kempe's proof said nothing about multiple trials (whatever that means). Thus, Kempe's proof was flawed.
>If Kempe is to be allowed only one chance; how about a slight >change to Heawood's coloring before Kempe takes over?
Once again, your analysis would have to deal with _all_ possible counterexamples, not just the one Heawood supplied.
quasi



