Re: Four Color Theorem


bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
a.khanm@xxxxxxxxx wrote:
bill wrote:
Hypothesis: A simple loopless maximal planar graph with a 5-degree
vertex cannot be a
minimal counter example to the four color theorem!.

It follows from the four colour theorem. However, proving it directly
> > > > > > is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.

Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.

This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.

My proof is based on the assumption that the following graph is not 4-chroma.
[The drawing below is correct in the "print" mode}

If you're going to post plain text which is supposed to line up, use a
proportional font, like Courier.

|..............| Internal chord
|--------------| External {B-C-B} Kempe chain
D <== A-----B-----C-----B------D ==> A
|--------------|--------------| External {A-C) & {C-D}
Kempe chains

The graph is planar. The {B-C-B} chain may cross the {A-C} & {C-D} chains
at common 'C' vertices.

It looks like you made Kempe's mistake again.

The graph is an attempt to find a feasible method of forcing a 4-coloring on a
chordless 5-cycle graph, without adding any chords. Without the internal chord
It is supposed to be a graph that cannot be 3-colored! With the "internal" chord,
theoretically, it cannot be properly 4-colored..

Theoretically; but (as I've told you before), if you have a planar
graph with a face of size >= 4, then there is more than one coloring.
All you have done is made one coloring fail to work; you haven't done
anything to the rest, which may still work. (In fact, in the graph G
with a pentagon, there are at least 2^(5-3) = 8 colorings. I'm not sure
whether this counts permutation of the colors or not.)

[BTW , 2^(5-3) = 4 not 8]

My point still holds.

A 3-coloring of the pentagon (P) does not work because G would be
4-colorable. A 5-coloring of P does not work because H would not be
4-colorable. If there is only one 4-coloring, all the others must be
3-colorings or 5-colorings, which inherently don't work!

Nice speech, but it also shows that you aren't on topic here. (Later
on, I do agree that in a minimal counterexample, the pentagon P will be
4-colored, and there's only one way to do that, up to isomorphism and
changing colors.)

The point is: You can't assume there is only one coloring of G-v.

I am not assuming a single coloring for G-v! I am only assuming a single
coloring for P.

That is not true, either.

Maybe so, but for the purposes of discussion, I am "assuming" that it is true;
just as I am assuming that P is not 3-colorable.

Assuming that P is not 3-colorED is part of the 4CT, and is okay. But
the issue of whether there is only one way for P to be 4-colored cannot
be assumed; it is one of the main issues.

The proper statement is: There is only a single 4-coloring for P,
UP TO SYMMETRY and permutation of colors. When you add an edge
to G-v, you are destroying the symmetry, and you need to account for that.

I'll agree that for a specific configuration for G-v. one coloring of G-v will make
vertices a & c the same color, while another coloring of G-v will make vertices
b & d the same color. But I do not understand how the chord between a & c
destroys the symmetry?

I described this below.

Suppose your pentagon P consists of the vertices a, b, c, d, e, in that
order (and edges ab, bc, cd, de, ea):

(1) Draw it and label it on a piece of paper.
(2) Cross out the a and write b in its place, cross out the old b, and
write a c in its place, cross out the old c and write a d in its place,
and cross out the old d and write an e there, and cross out the old e
and write an a there.
(3) Look at the new labelling you have; you have edges ab, bc, cd, de,
and ea (with the new labels). These are all the edges that were in the
original pentagon P.

Now, draw P and add the edge ac. Replace the labels like you did in
step (2). Your new graph will have edges ab, bc, cd, de, ea, and bd.
This is NOT the graph consisting of P plus the edge ac. This is what I
mean by destroying the symmetry.

Any coloring of G-v is acceptable as long as it results in a
4-coloring of P. If there is a coloring of G-v that does not result in a
4-coloring of P, then G wil be 4-colorable!

You get a coloring C from the minimality of G, and show that there is a
graph H where the coloring C doesn't work. However, there _are_ other
colorings of G-v which are proper for H.

Are you saying that after the internal chord is added to P, that the graph H
can arbitrarily be recolored to make P 4-colored again?

Remove the word "arbitrarily", and I'll say yes.

In that case you
would have to recolor one of the vertices at the end of the chord. But which
one? Why one and not the other? If either, why not both? If both, then
P is 3-colorable and G is 4-colorable.

The problem is that when you added a chord, you destroyed the symmetry
of P.* The colors of the ends of that chord might each be used once on
P, or one might be used once and the other used twice.

The chord connects vertices of the same color! I am assuming that P is
colored before the chord is added.

I'm assuming it's colored afterwards.

For specificity, let's say the pentagon P consists of vertices a, b, c,
d, and e, in that order, and that you add the chord ac. Now you have
two types of 4-colorings of P+ac (up to permutation of colors and
symmetry of P+ac):

Red: a
Blue: c
Green: b, d
Yellow: e

Red: a
Blue: c,e
Green: b
Yellow: d

In what way are these two types of 4-colorings?

In the first one, the color which is used twice is not used on either
of the ends of ac; in the second one, it is.

The only symmetry that you have left for P+ac is exchanging a with c, d
with e, and keeping b fixed. You do not have rotational symmetry, as P
had (replace a with b, b with c, etc.)

Perhaps not, but why is that significant?

Because you can no longer assume that P+ac is colored in one particular
way. There are two cases to consider, not one.

* There is the possibility that there is a chord outside of P already
in G. But in that case, you have a copy of K4, and it is well-known
that no minimal counterexample of the 4CT contains K4.

If there is, there is! No big deal.

Yes, that's what I said.

I still say that there is only one 4-coloring of a pentagon.

That is true.

I have not made it fail. I jusr have not found the configuration that will
make it work.

Just for discussion, suppose you or I find a configuration that does work?
Then I add a couple of chords to maximize graph H. Graph H still has
fewer vertices than G. If H is not 4-colorable, then G is not an mce
because it is not minimum. One of the chords connects two vertices
with the same color. Unless one or more of the vertices of H can be
recolored, H is not properly 4-colorable. And if one or more vertices can
be recolored, then perhaps H can be properly 3-colored.

How can I make you understand what I am trying to do?

Essentially, a 4-coloring of the pentagon (P) is the only way to make graph H
4-colorable and graph G not 4-colorable! If P is 4-colorable, then two vertices
have the same color. If a chord is added between these two vertices, H will
still be smaller than G. This chord makes the colorability of H uncertain.

If P is 3-colorable, then G is 4-colorable!
If H is not 4-colorable, then G is not minimal!
If P is 4-colorable, but not 3-colorable; then and only then G is an mce!

The graph has to come before the coloring. Sure, if you have a coloring
C, you can find a graph for which C is not a proper coloring. But
that's not how the 4CT is worded.

Can you explain the above observation in the context of the mce/4CT?

Imagine you have a machine M which takes, as input, a planar graph G,
and produces a 4-coloring of G as output. (If one exists.) The 4CT
simply states that for every input, there is (at least) one output;
that is, you cannot find a planar graph G that causes M to "crash".

A minimal counterexample is a graph G which crashes M, but at the same
time, M will produce an output for any graph with fewer vertices than
G.

You are taking the output of a graph G-v and coming up with a new graph
H. The output from G-v does not work for H, but that does not imply
that the machine will crash with H as an input. So you don't have your
contradiction that proves the 4CT yet.

If H is not 4-colorable, won't the machine crash?

Yes. But H can still be 4-colorable; the output would just be something
other than the output for G-v.

H is 4-colorable only if P is 4-colorable.

If H is 4-colorable, then P is 4-colorable. But the converse doesn't
have to hold.

Adding two chords to P makes its 4-colorability less than 100% probable!

No, the resulting graph is 4-colorable. In fact, P is 3-colorable.

[It requires two chords to maximize H]

Finally, is it possible to prove that P is always 4-colorable and at the same time
prove that it is not 3-colorable?

As I mentioned above, P plus two edges is always 3-colorable. The
question is whether that 3-coloring extends to the rest of H. This will
require a substantial reworking of the coloring of G-v, if there is a
4-coloring of H. Since you don't know anything about what G (and hence
H) looks like "outside" of P, there's no way to answer the question.
This is where things like Kempe chains come in handy.

(Obviously, we "know" that H must be 4-colorable, because H has fewer
vertices than G. But this won't give us a contradiction.)

--- Christopher Heckman

I expect that someone will reveal the flaw. Then I will observe that
you can't force a 4-coloring without at least 3 external chains and
that this is the only way to get three chains.

With only two chains, the colors of only three vertices may be "forced"
. [Each
vertex has only two neighbors. Therefore, there are at least two
color options
for each vertex. "Forcing" means removing all but one option!]

This leaves 2 vertices whose colors cannot be forced by chains; but by some
unknown configuration?

Before I go any further, does anyone care to comment on the 3-chain configuration?
Also, any suggestions as to how a specific vertex can be forced to be a specific
color?

Exactly what was "Kempe's mistake"?

See http://www.stonehill.edu/compsci/LC/Four-Color/Four-color.htm . Two
graphs for which his proof fails are given by:

http://mathworld.wolfram.com/KittellGraph.html (23 vertices)
http://mathworld.wolfram.com/ErreraGraph.html (17 vertices)

I think that "Kempe's mistake" must have been that he could not prove
that his method could properly 3-color the cycle graph? I don't care
if
the cycle graph can be 3-colored or not!

regards

---Bill J.



--- Christopher Heckman

.

Relevant Pages

  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... You can't assume there is only one coloring of G-v. ...
    (sci.math)
  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... that no minimal counterexample of the 4CT contains K4. ...
    (sci.math)
  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... that no minimal counterexample of the 4CT contains K4. ...
    (sci.math)
  • Re: Four Color Theorem
    ... It follows from the four colour theorem. ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ...
    (sci.math)
  • Re: Four Color Theorem
    ... It follows from the four colour theorem. ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ...
    (sci.math)
Quantcast