Re: Minimal Counter-example to the 4CT.


bill wrote:
Chip Eastham wrote:
bill wrote:
Chip Eastham wrote:
bill wrote:
Proginoskes wrote:
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.

OK! You start out with a 4-colorable graph, add a vertex and get a
graph that is not
4-colorable!

Call the 5-chroma graph G and the 4-C graph (G-v) and the added vertex
v_1.
If you remove vertex v_i, (where i = 2,3,4, ... n) from G; do you
always get a 4-colorable graph or do you sometimes get a graph that is
not 4-colorable?

Hypothetically? Yes, without using the planarity of the graphs involved
and the 4 Color Theorem, you might have a situation in which adding
a vertex turns a 4-chroma graph into a 5-chroma graph, and removing
a _different_ vertex leaves you with a 5-chroma graph.


Would it be helpful to give an example on a torus (genus 1 surface),
where there can actually be 5-chroma graphs?


Of course it is _sufficient_ to prove 4CT if you can show "inductively"
that adding a vertex to a 4-chroma graph always results in another
4-chroma graph, provided the result is planar. A posteriori we know
that to be true, as a consequence of 4CT. However no one knows
how to prove 4CT in that fashion.


Bill wrote:

But if we assume that the graphs are planar and the 4CT is involved,
what then?
Consider only those cases for which G is an mce?

Let me try to explain my position again

(G-v) is 4-Colorable. If we add a vertex it becomes 5-chroma..
Is it possible that (G-v) can also be made 5-chroma by adding one or
or more edges,
but without adding any more vertices?

Hi, Bill:

All I understand of you position is that graph G without vertex v
is 4-colorable. Presumably G is planar, and has one or more
edges connecting v to other vertices in G (otherwise removing
v is not very interesting as far as the chromatic number goes).

"If we add a vertex it becomes 5-chroma" is unnecessarily
imprecise. If you are assuming G is a "minimal counter-
example to the four color theorem" then you are assuming
G is 5-chroma.

Bill wrote:

I am NOT assuming that G is a mce! I am assuming only that G is planar
and 5-chroma!

The significance of the distinction eludes me. If you assume G is
a counterexample to the four color theorem, then some subgraph
of G will necessarily be a minimal counterexample. [Note that the
approach is cutting down from a "big" counterexample to get a
minimal one, rather than "expanding" a non-counterexample (a
4-chroma planar graph) somehow into a counterexample.]


If G is an mce, then there are no 5-chroma planar graphs with fewer
vertices. If we remove a vertex from G we have a planar graph (G-v)
with fewer vertices. Therefore,
If G is an mce, then (G-v) must be 4-colorable. . .

I would quibble about the first of these three statements. Claiming
that G is a "minimal counterexample to the four color theorem"
means that no subgraph of G is a counterexample. However it is
possible a priori that nonisomorphic minimal counterexamples
exist, and possible that some have fewer vertices than others. You
could always pick one that has a minimum number of vertices,
among counterexamples to the 4CT, for your graph G, and then
the first statement would be justified. To elaborate the description,
such G would be a minimal counterexample to the 4CT with a
minimum number of vertices.

Since every vertex in G is at least degree 5, (G-v) cannot be maximal!.

I don't know how to prove what you claim in the antecedent portion
of this statement. Note that it is possible to construct a minimal
4-chroma planar graph (not one with "minimum number of vertices"
but nonetheless minimal with respect to requiring four colors among
planar graphs) in which there are as many vertices of degree 3 as
one wishes.

Even if we assume G is a "minimal counterexample with a minimum
number of vertices" I do not know how to prove that every vertex in G
has degree at least 5. The only reason I know the corresponding
fact for minimal 4-chroma planar graphs with minimum number of
vertices is because it is possible to have K4, four mutual adjacent
vertices, in the plane, but since K5 is not planar, no similar proof
would work for the 5-chroma proposition.
have such a graph

In the consequent portion of this statement you introduce the word
"maximal". I don't understand the context of that adjective. With
respect to what property is (G-v) not maximal?

It has not been proven that maximizing (G-v) cannot make it 5-chroma!
There does not seem to be any rule against maximizing (G-v). If (G-v)
can be made 5-chroma without adding any vertices; then G cannot be
an mce!

I am merely investigating the possibility of proving that (G-v) can
always be made 5_chroma by maximizing it.

[more discussion of "maximizing"]


I had written: Of course the 5-color theorem was already proved for
planar graphs by pretty elementary methods

What were they?

In 1879 Alfred Kempe published what he thought was a proof of the
Four Color Theorem. More than ten years later, Percy Heawood
showed that Kempe's proof contained a subtle but fatal error, and
he showed that what one is actually able to obtain by the method
of Kempe's argument is the weaker result that five colors at most
are needed for any planar graph.

A brief outline of the proof is given by the Wikipedia article, here:

http://en.wikipedia.org/wiki/Five_color_theorem

.

Relevant Pages

  • Re: 4CT
    ... color the smaller graph ... vertex v leaves graph (G-v) at least two edges short of maximality. ... The same coloring ... If G is a minimal counterexample, then ANY planar graph with fewer ...
    (sci.math)
  • Re: Minimal Counter-example to the 4CT.
    ... get a 5-colorable planar graph. ... but a minimal counterexample to the ... Call the 5-chroma graph G and the 4-C graph (G-v) and the added vertex ...
    (sci.math)
  • Re: Some Thoughts on the Four Color Theorem
    ... planar graph which are not planar. ... sometimes called a "separating triangle". ... planar graph is 3-edge colorable, ...
    (sci.math)
  • Re: Some Thoughts on the Four Color Theorem
    ... planar graph which are not planar. ... sometimes called a "separating triangle". ... planar graph is 3-edge colorable, ...
    (sci.math)
  • Re: Some Thoughts on the Four Color Theorem
    ... planar graph which are not planar. ... sometimes called a "separating triangle". ... planar graph is 3-edge colorable, ...
    (sci.math)