Re: Minimal Counter-example to the 4CT.


Chip Eastham wrote:
bill wrote:

In one sense, "the Minimal Counter-example to the 4CT" says that there
exists a 4-colorable planar graph, to which you can add a vertex and
get a 5-colorable planar graph.

Perhaps this is hair splitting, but a minimal counterexample to the
four color conjecture (now theorem) involves a 4-colorable planar
graph to which one adds a vertex and gets a planar graph that is
not 4-colorable.

Every 4-colorable graph is also 5-colorable.

Literally a minimal counterexample would be a planar graph that is
not 4-colorable, but in which the removal of any vertex produces a
4-colorable (necessarily planar) graph.

That's what I meant when I said "[being a minimal counterexample to the
4CT] says a lot more than [there existing a 4-colorable planar graph,
where if you add a vertex, you get a 5-colorable planar graph]", bill.

--- Christopher Heckman

.

Relevant Pages

  • Re: Four Color Theorem
    ... > exists a planar graph with fewer vertices whose chromatic number is ... it was shown how this statement implies the 4CT. ... In the new proof of the 4CT, the idea of a "minimal counterexample" was ...
    (sci.math)
  • Re: Minimal Counter-example to the 4CT.
    ... in treating any potential mce/4CT as a maximal planar graph One ... that weak notion of minimal counterexample as having a minimal ... You mention "the analogy" but I'm not aware of any ...
    (sci.math)
  • Re: Minimal Counter-example to the 4CT.
    ... bill wrote: ... get a 5-colorable planar graph. ... Perhaps this is hair splitting, but a minimal counterexample to the ...
    (sci.math)
  • Re: Minimal Counter-example to the 4CT.
    ... get a 5-colorable planar graph. ... Perhaps this is hair splitting, but a minimal counterexample to the ...
    (sci.math)
  • Re: Minimal Counter-example to the 4CT.
    ... Chip Eastham wrote: ... There are significant advantages ... in treating any potential mce/4CT as a maximal planar graph One ...
    (sci.math)