The Math Forum

Search All of the Math Forum:

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

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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 ]

Posts: 12,067
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

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

>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

>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.


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

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.