On Tuesday, July 2, 2013 6:14:12 PM UTC-7, quasi wrote: > 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
Every counter example will have a set of six vertices that if 4 colored will have two adjacent vertices of the same color. Call this an "improper" 4-coloring as opposed to a "proper" 4-coloring, where there are no adjacent same colors. In a different thread you said this was IMPOSSIBLE in a planar graph. The counter examples are colorings of planar graphs. Is there a problem?