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: 11,749
Registered: 12/4/04
Re: A Simple Proof of The Four Color Theorem
Posted: Jul 3, 2013 4:53 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Tuesday, July 2, 2013 6:42:43 PM UTC-5, bill wrote:

> If Kempe's strategy had been applied to the coloriing with the two adjacent vertices with the dame color; it would have been successful.
> Why do we expect Kempe's strategy to succeed on the first trial when no other method is under the same restrictions?

Kempe's argument involved taking a particular chain and changing the colors in the chain. He then claimed that this change in the colors would not introduce any new problems, but would only "solve" or "reduce" the number of problems. What Heawood did was show that this second claim was incorrect: there were graphs in which following the argument would *not* reduce the number of problems, and so the proposed algorithm for 4-coloring would not terminate.

Kempe *claimed* that his algorithm would *always* work "on the first trial". That claim was incorrect. Therefore, the argument proposed was incorrect.

This does not mean that a modification of the argument could not succeed, nor does it mean that the conclusion is false. It means, simply, that the proposed argument *as given*, was incorrect.

> If Kempe is to be allowed only one chance;

It's not a matter of what "Kempe is [...] allowed". Kempe made a specific claim: that his algorithm, *as given*, would always terminate. Heawood proved that this was not the case, and therefore, that Kempe's specific claim is incorrect. What exactly is the problem?

> how about a slight change to Heawood's coloring before Kempe takes over?

There's nothing to "take over." If I claim that I can produce three currently minted valid US coins that will add up to 4 cents, then my claim does not become correct if you show you can do it with 4 coins, or that you can do it with coins that are not currently minted. We are not discussing the propositino of whether it is possible to find valid US coins that will add up to 4 cents, but only my specific claim that it can be done with three currently minted valid US coins.

The same is true of Kempe's argument: he makes a specific argument that asserts that his procedure will always result in a 4-coloring, *as given*. Heawood showed that the procedure, as given by Kempe, did not in fact result in a 4-coloring. That's all that is needed to invalidate the argument.

Arturo Magidin

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.