|
|
| Author |
Message |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
 Posted: Sun Jul 16, 2006 5:04 am Post subject:
Re: Four Color Theorem
|
|
|
icahit@gmail.com wrote:
| Quote: | Is this an algorithm or a program for coloring the maps?
|
Program.
--- Christopher Heckman
| Quote: | Han de Bruijn wrote:
Proginoskes wrote:
Is a "coloring algorithm" really necessary in a proof of the 4CT?
No, but you usually get one as a freebie.
Claims, claims ... But I didn't _see_ any anywhere, except my own:
http://hdebruijn.soo.dto.tudelft.nl/fcp/index.htm
Han de Bruijn |
|
|
| Back to top |
|
 |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sun Jul 16, 2006 5:06 am Post subject:
Re: Four Color Theorem
|
|
|
icahit@gmail.com wrote:
| Quote: | In all your examples after running greedy (algorithm) when you run
minimal coloring the outer-region of the map has received a valid
color. This at least verify my result that for any connected map the
outer-region can be taken as a part of a region of the map or more
techincally "spiral-segment" of a spiral chain of a maximal planar
graph is 3-colorable. Can you prove that this is the case in your
program for any map?
|
Sure, you can include the outer region ("infinite face") in the map.
This is because of a well-known result that states the 4CT is true for
the plane iff it is true for the sphere.
--- Christopher Heckman
| Quote: | Han de Bruijn wrote:
Proginoskes wrote:
Is a "coloring algorithm" really necessary in a proof of the 4CT?
No, but you usually get one as a freebie.
Claims, claims ... But I didn't _see_ any anywhere, except my own:
http://hdebruijn.soo.dto.tudelft.nl/fcp/index.htm
Han de Bruijn |
|
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sun Jul 16, 2006 5:18 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
a.khanm@gmail.com 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. 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.
| Quote: | 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.
| Quote: | 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.
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
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.)
* 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.
| Quote: | 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.
--- Christopher Heckman
| Quote: | 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 |
|
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Sun Jul 16, 2006 8:44 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
a.khanm@gmail.com 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.
| Quote: | 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?
| Quote: | 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.
| Quote: |
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?
| Quote: |
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?
| Quote: |
* 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.
| Quote: |
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. Adding two chords to P
makes its
4-colorability less than 100% probable! [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?
regards
---Bill J
| Quote: | --- 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 |
|
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sun Jul 16, 2006 5:12 pm Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | 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@gmail.com 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | * 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | [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
| Quote: | 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 |
|
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Mon Jul 17, 2006 12:09 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | 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@gmail.com 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.
|
I suppose that I should know why this is relevant but I don't? I am
only
concerned with vertex colors.
| Quote: |
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.
How do you know that P is not 3-colorable, if you don't color it? |
| Quote: | 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.
Relevancy? |
| Quote: | 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.
|
Another seemingly irrelevant comment?
| Quote: |
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.
|
If P is 3-colorable, then G is 4-colorable.
| Quote: |
[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.
|
Let's start at the begining.
1. G-v is an induced subgraph of G. P is a cordless 5-cycle graph
in G-v consisting of the 5 neighbors of v.
2. We stipulate a configuration of G-v that forces a 4-coloring
on the 5 vertices of P.
3. G-v is 4-colorable
4. For purposes of discussion, we assign arbitrary colors to the
vertices of P;
say " A, B, A, C, D".
5. A chord of P is drawn between the two vertices that are colored
'A'.
6. We have maintained the fiction that G is an mce up to this
point. I am not
sure how to do it from here?
| Quote: | This is where things like Kempe chains come in handy.
Kempe chains are hand but not handy "enough"! I am not aware of the |
"things" that are "like Kempe chains"?
| Quote: | (Obviously, we "know" that H must be 4-colorable, because H has fewer
vertices than G. But this won't give us a contradiction.)
But what if H is NOT 4-colorable? |
regards
---Bill J
| Quote: | --- 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 |
|
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Mon Jul 17, 2006 5:45 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes wrote:
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@gmail.com 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.
I suppose that I should know why this is relevant but I don't? I am only
concerned with vertex colors.
|
(1) Did you actually do the exercise?
(2) It is only because of symmetry that you can assume that a and c are
colored the same color, b with a new color, d with another new color,
and e with yet another new color.
Otherwise, you'd have five cases to settle:
(i) a and c colored the same
(ii) a and d colored the same
(iii) b and d colored the same
(iv) b and e colored the same
(v) c and e colored the same
Without symmetry, you would have to do them ALL.
| Quote: | 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.
How do you know that P is not 3-colorable, if you don't color it?
|
But if you color P+two edges after constructing it, you only need 3
colors. That's my point. Take a pentagon P, with vertices in the order
a,b,c,d,e. Add the edges ac and ad. Now color a Red, b and d Green, and
c and e Blue.
| Quote: | 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.
Relevancy?
|
How can you not see how it's relevant? You cannot change a coloring of
one type into the other by using the reflective symmetry of P+ac. (The
reflective symmetry of P+ac is exchanging the labels "a" and "c", "d"
and "e", and keeping "b" labelled as "b". EXERCISE: Verify this.)
| Quote: | 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.
Another seemingly irrelevant comment?
|
Remember the extremely long odd cycle, and the discussion about how you
can't look at just the vertices within a distance of 100 in order to
determine whether a graph is k-colorable?
EXERCISE: Let G be the pentagon a,b,c,d,e, with the edge ac added. Now
you can color the neighbors of b (a and c) with 2 colors. (Do this.)
But the entire graph requires 3 colors. (Prove this.) Thus the
neighborhood of b needs FEWER colors than the entire graph.
| Quote: | 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.
If P is 3-colorable, then G is 4-colorable.
|
You're making the same mistake over and over again.
EXERCISE. Let G be the pentagon a,b,c,d,e, let P be the subgraph of G
consisting only of the vertices {a,c}, and H the subgraph of H
consisting only of the vertices {a,b,c}. (a) Show that you can color P
using only one color. (b) Show that you can color H with two colors.
(c) Show that G requires 3 colors.
To answer your question about relevance, here's the analogy: You start
with a graph G, delete a vertex (here, it will be the vertex b), and
color G-b. Then you look at the graph which consists of the neighbors
of b and call it P. What you have shown above is that the following is
FALSE: "If P is k-colorable, then G is (k+1)-colorable."
| Quote: | [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.
Let's start at the begining.
1. G-v is an induced subgraph of G. P is a cordless 5-cycle graph
in G-v consisting of the 5 neighbors of v.
2. We stipulate a configuration of G-v that forces a 4-coloring
on the 5 vertices of P.
3. G-v is 4-colorable
4. For purposes of discussion, we assign arbitrary colors to the vertices of P;
say " A, B, A, C, D".
|
And let's assign names to those vertices: a,b,c,d,e.
| Quote: | 5. A chord of P is drawn between the two vertices that are colored 'A'.
|
And let's call the whole graph H, after you do all of this.
| Quote: | 6. We have maintained the fiction that G is an mce up to this point. I am not
sure how to do it from here?
|
Presumably, you want to show that the new graph H is not 4-colorable,
which contradicts the assumption that G was a minimal counterexample.
I don't know how to do this quickly. If I did, I'd publish the world's
shortest proof of the 4CT. (Actually, if it was possible to do quickly,
someone _else_ would have already done it.)
| Quote: | This is where things like Kempe chains come in handy.
Kempe chains are hand but not handy "enough"! I am not aware of the
"things" that are "like Kempe chains"?
|
I don't know, either, but "something like a Kempe chain" would tell you
something about the structure of G, and you could get some idea of
what's going on.
A Kempe chain would keep you from saying that you can recolor vertex b
with color D (which would make G 4-colorable, whereupon we'd be done),
and would tell you _something_ about the graph G outside of P (the
existence of a path of vertices from b to e, alternately colored B and
D).
| Quote: | (Obviously, we "know" that H must be 4-colorable, because H has fewer
vertices than G. But this won't give us a contradiction.)
But what if H is NOT 4-colorable?
|
That is what you need to show, and once again, I don't know how you
would do it. H could be 4-colorable, but the 4-coloring of H will be
substantially different from that of G-v. For instance, the vertices
a,b,c,d,e, might be colored A,B,C,D,B, in that order.
One last comment: I am not kidding about doing the exercises. They will
help give you some intuition about how colorings behave, and you can
avoid a lot of the elementary traps that so many amateurs run into.
--- Christopher Heckman
| Quote: | 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 |
|
|
| Back to top |
|
|
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Mon Jul 17, 2006 7:56 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | Sure, you can include the outer region ("infinite face") in the map.
This is because of a well-known result that states the 4CT is true for
the plane iff it is true for the sphere.
|
Yes, but the _clipped_ infinite face has been included with my program,
of course.
Han de Bruijn |
|
| Back to top |
|
|
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Mon Jul 17, 2006 8:13 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | (2) Anyone can code a map-coloring algorithm; [ ... ]
|
Sure. Where is the code that I can download and run?
| Quote: | Claims, claims ... But I didn't _see_ any anywhere, except my own:
|
Han de Bruijn |
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Tue Jul 18, 2006 4:08 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | 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:
Proginoskes wrote:
bill wrote:
a.khanm@gmail.com 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.
I suppose that I should know why this is relevant but I don't? I am only
concerned with vertex colors.
(1) Did you actually do the exercise?
|
Yes. But I can always get P+ac back by relabelling lhe vertices.
| Quote: |
(2) It is only because of symmetry that you can assume that a and c are
colored the same color, b with a new color, d with another new color,
and e with yet another new color.
|
If P requires at least 4-colors to be properly colored, then two
vertices must
have the same color! I named these two vertices 'a' and 'c' for
convenience!
| Quote: |
Otherwise, you'd have five cases to settle:
(i) a and c colored the same
(ii) a and d colored the same
(iii) b and d colored the same
(iv) b and e colored the same
(v) c and e colored the same
Without symmetry, you would have to do them ALL.
|
NO! In case (i) I would put the chord between a & c. In case (ii), I
would
put the chord between a & d. ... In case (v), I would put the chord
between
c & e. Or I could relabel the vertices so that a & c always have the
same
color!
| Quote: | 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.
How do you know that P is not 3-colorable, if you don't color it?
But if you color P+two edges after constructing it, you only need 3
colors. That's my point. Take a pentagon P, with vertices in the order
a,b,c,d,e. Add the edges ac and ad. Now color a Red, b and d Green, and
c and e Blue
|
Then G would be 4-colorable!
| Quote: |
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.
Relevancy?
How can you not see how it's relevant? You cannot change a coloring of
one type into the other by using the reflective symmetry of P+ac. (The
reflective symmetry of P+ac is exchanging the labels "a" and "c", "d"
and "e", and keeping "b" labelled as "b". EXERCISE: Verify this.)
|
The reason that I cannot see why its relevant is that I don't know why
I should want to or need to relabel the vertices?
Why should I keep "b" labelled as "b"?
| Quote: |
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.
Another seemingly irrelevant comment?
Remember the extremely long odd cycle, and the discussion about how you
can't look at just the vertices within a distance of 100 in order to
determine whether a graph is k-colorable?
|
But all of the vertices in G-v are not in the long odd cycle?
| Quote: |
EXERCISE: Let G be the pentagon a,b,c,d,e, with the edge ac added. Now
you can color the neighbors of b (a and c) with 2 colors. (Do this.)
But the entire graph requires 3 colors. (Prove this.) Thus the
neighborhood of b needs FEWER colors than the entire graph.
|
If G is a pentagon, then G cannot be a mce/4CT .
| Quote: |
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.
If P is 3-colorable, then G is 4-colorable.
You're making the same mistake over and over again.
EXERCISE. Let G be the pentagon a,b,c,d,e, let P be the subgraph of G
consisting only of the vertices {a,c}, and H the subgraph of H
consisting only of the vertices {a,b,c}. (a) Show that you can color P
using only one color. (b) Show that you can color H with two colors.
(c) Show that G requires 3 colors.
To answer your question about relevance, here's the analogy: You start
with a graph G, delete a vertex (here, it will be the vertex b), and
color G-b. Then you look at the graph which consists of the neighbors
of b and call it P. What you have shown above is that the following is
FALSE: "If P is k-colorable, then G is (k+1)-colorable."
You are confusing things by calling the pentagon G. The pentagon (P) |
is
a subgraph of G, which is a potential mce/4CT. Somewhere back the
dark ages, I started out to prove that if G had a vertex of degree 5,
it could
not be a mce/4CT! Where did I go wrong?
| Quote: | [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.
Let's start at the begining.
1. G-v is an induced subgraph of G. P is a cordless 5-cycle graph
in G-v consisting of the 5 neighbors of v.
2. We stipulate a configuration of G-v that forces a 4-coloring
on the 5 vertices of P.
3. G-v is 4-colorable
4. For purposes of discussion, we assign arbitrary colors to the vertices of P;
say " A, B, A, C, D".
And let's assign names to those vertices: a,b,c,d,e.
5. A chord of P is drawn between the two vertices that are colored 'A'.
And let's call the whole graph H, after you do all of this.
6. We have maintained the fiction that G is an mce up to this point. I am not
sure how to do it from here?
Presumably, you want to show that the new graph H is not 4-colorable,
which contradi |
| | |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
