Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: A Simple Proof of The Four Color Theorem
Replies: 10   Last Post: Jul 3, 2013 6:36 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
quasi

Posts: 10,226
Registered: 7/15/05
Re: A Simple Proof of The Four Color Theorem
Posted: Jul 2, 2013 9:23 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

bill wrote:
>quasi wrote:
>>bill wrote:
>>>
>>>Kempe's method was accepted as proof of the FCT until
>>>Heawood created his counter-example.
>>>
>>>Suppose that there was a simple way to 4-color 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 4-colored 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 4-colorability 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 4-colored 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 4-colorable,
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 4-coloring. 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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.