|
|
| Author |
Message |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
 Posted: Thu Jul 20, 2006 6:04 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes wrote:
bill wrote:
Proginoskes wrote:
icahit@gmail.com wrote:
I must be careful when I give an answer to your question. Yes my proof
has not yet published but I think it has been passed through extensive
public review in the last two years. I have given several seminars in
the mathematical departments. The bottom line is that, no one yet and
I trust, no one will be given serious comments against its correctness.
I have my doubts, especially in Cahit's paper which "settles"
Steinberg's Conjecture. In particular, I derived the conditions under
which a "triangulated ring" is 3-colorable, and they do not match
Cahit's. That, and my increased workload during the academic year, have
kept me from looking at more of the problem.
What is "Steinberg's Conjecture"? What is a "triangulated ring"?
Steinberg's conjecture states that a planar graph without any cycles of
length 4 or 5 can be 3-colored
Amateur's Proof of the SC: Every planar graph that is not 3-colorable has
at least one vertex that is the hub of an even-order wheel graph!
|
I assume by "even order" you mean an even number of vertices (and the
central vertex thus has odd degree). If so, you have made a classic
mistake: Confusing "P implies Q" with "Q implies P" ("Affirming the
Consequent").
| Quote: | Such a graph must have a cycle of length 4 or 5. The graph with four
mutually adjacent vertices provides the cycle of length 4. The wheel graph
with 5 or more spokes provides the cycle of length 5.
|
Another reason that this "proof" is wrong is that it also shows that
any planar graphs without 4-cycles is 3-colorable. (Two triangles that
share an edge provide a 4-cycle on their own.) And this is simply
wrong; there is a planar graph with no 4-cycles which is not
3-colorable.
I can't seem to find an image of this last one, so I'll sketch one and
post the URL.
--- Christopher Heckman
| Quote: |
"Triangulated ring" is a term invented by Cahit. It refers to a cycle
of length n, surrounded by triangular faces (whose 3rd vertex points
away from the cycle), then by triangular faces which point "towards"
the cycle, and then you have a cycle on the outside.
|
| Quote: |
It is my opinion that the proofs should be worked out in more detail.
It is true that in the final publisheable form I will have to add a few
things and delete some unneccessary figures and explain my spiral-chain
coloring algorithm in more detail, that is three-coloring of the spiral
segments and additional stuff on three-plus-one spiral chain coloring
and also adding may be a new section for the three-edge coloring of
(bridgeless) cubic planar graphs. I will going to present my proof in
the ICM2006, Madrid in August (
http://icm2006.org/v_f/web_UC.php?CodiSeccio=14&CodiTipusEvent=4sc&Ordenacio=ae&Format=UC4sc)
and based on the feedback I receive I am going to submit to a proper
journal. The only thing that I would say about Dharwadker's "proof" of
the 4CT is that there is no description of an coloring algorithm in his
proof.
Cahit
a.khanm@gmail.com wrote:
What became of your proof of the four colour theorem? Usually people
tend to make the same old mistakes in proving the elusive theorem. Have
you found any errors yet or do you still think that your proof is
correct? Another person by the name of Ashay Dharwadker has claimed to
have proven the four colour theorem but his proof never made it to a
journal. What is the current status of your proof?
icahit@gmail.com wrote:
May be the answer to Bill's question is in my response in another group
at
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1150590683
Cahit
Proginoskes 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.
But a variation of induction is the backbone to reduction, a technique
that both Appel and Haken, and Robertson Sanders Seymour Thomas used to
find a proof.
--- Christopher Heckman |
|
|
| Back to top |
|
 |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Thu Jul 20, 2006 6:41 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:
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.
Then you missed the point of the exercise.
Obviously! What is the point?
|
Destroying symmetry means the number of cases increases.
| 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!
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.
And you have thus done all 5 cases. I rest my case.
Or I could relabel the vertices so that a & c always have the same
color!
In this case, you're taking advantage of symmetry. I rest my case.
I still do not understand why I need to account for destroying the
symmetry?
|
Because not all 4-colorings of P+ac are equal. If you have two
4-colorings of P, you can use symmetry operations and color shuffling
to turn one into the other. If you have two 4-colorings of P+ac, this
is not necessarily the case. You cannot turn one type of coloring of
P+ac below into the other.
Try it.
| 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!
No. In order to see whether G is 4-colorable, you need to color ALL of
G, not just a piece of it. It may happen that you need to have 4
different colors on P+2e in order to color G. (This is called
"extending a coloring" from one graph to another.) Remember, the only
coloring you have for the entire graph requires P+2e to be colored with
5 colors.
By definition, G is 4-colorable if P is 3-colorable. This is a basic premise of the
proof.
|
No; that only applies to P and the central vertex v. You may need a
fifth color to color the rest of G. You have the burdon of proof, i.e.,
you have to show that this is not the case.
| Quote: | *I do not have a coloring (per se) for the entire graph!.
|
Then you haven't proven the 4CT. You have the burdon of proof, by
stating that you have proved it. This means that you need to be able to
handle any relevant questions that I may ask. Such as: "How can you
guarantee that the _whole graph_ is 4-colored, not just P and its
neighbors?"
| Quote: | I merely present a
scenario in which the proper coloring is in doubt; and ask you to choose
the proper coloring!*
|
That is my role in the situation.
| Quote: | Again, that was the point of one of the exercises.
Again, I missed the point!
|
Then you need to go back and re-read this post, including everything
that has been mentioned previously. I finding myself repetitiously
repeating myself over and over again in this thread.
| 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?
The only symmetry that P+ac has is the "reflective" one mentioned right
before the exercies.
A symmetry ("isomorphism") is properly defined as a bijective map f
from {a,b,c,d,e} to {a,b,c,d,e} such that (x,y) is an edge exactly when
(f(x),f(y)) is. The only symmetries that the graph P+ac has are the
functions defined by:
(i) f(a) = a, f(b) = b, f(c) = c, f(d) = d, f(e) = e, OR
(ii) f(a) = c, f(b) = b, f(c) = a, f(d) = e, f(e) = d.
Here's how you get started: A symmetry preserves degrees, so x and f(x)
have the same degree, for all x.
Look at the vertices of degree 3. The vertices of degree 3 are a and c,
so either
(i') f(a) = a and f(c) = c, OR
(ii') f(a) = c and f(c) = a.
Then b is a vertex adjacent to a and c, so f(b) must be adjacent to
f(a) and f(c), i.e., f(b) is adjacent to a and c (regardless of whether
we are in case (i') or (ii')). Now b is the ONLY vertex with this
property, so you must have
f(b) = b. Then you can continue and establish that the two functions
listed in (i) and (ii) above are the only ones with the symmetry
property.
wthdic? How does this effect the coloring?
|
I don't know what you mean by "this", but I'll assume it's the symmetry
(isomorphism) above.
The whole point of the symmetry discussion is that, given any two
colorings of P, you can transform one into the other by doing the
following, a finite number of times:
(a) a "rotation" (relabel the vertices so that old a = new b, old b =
new c, etc), OR
(b) swapping two color names.
For instance, if you start off with the coloring
x(a) = A, x(b) = B, x(c) = C, x(d) = D, x(e) = B,
you can transform it into the coloring
x(a) = B, x(b) = C, x(c) = D, x(d) = C, x(e) = A.
using the operations above.
Here's how:
x(a) = A, x(b) = B, x(c) = C, x(d) = D, x(e) = B [first coloring]
x(a) = A, x(b) = C, x(c) = B, x(d) = D, x(e) = C [swap colors B and C]
x(a) = C, x(b) = A, x(c) = C, x(d) = B, x(e) = D [rotate]
x(a) = D, x(b) = C, x(c) = A, x(d) = C, x(e) = B [rotate]
x(a) = A, x(b) = C, x(c) = D, x(d) = C, x(e) = B [swap colors A and D]
x(a) = B, x(b) = C, x(c) = D, x(d) = C, x(e) = A [swap colors A and B]
and we get the second coloring.
You _cannot_ do this when P is replaced by the graph P+ac.
| Quote: | Why should I keep "b" labelled as "b"?
It has to be. (Sorry about the pun.)
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?
Here I'm talking about the whole graph being a cycle. And I'm trying to
reinforce the point that you cannot just consider local vertices when
determining how a vertex v is colored; the coloring depends on the
entire graph.
Yes and no. The coloring of v depends solely upon the colors of its neighbors;
which in turn depends upon the coloring of the entire graph. For instance, if
v has only R, G, & B neighbors, nothing in the rest of the graph can force
v not to be Y In that sense the color of v does not depend on the coloring
of the rest of the graph.
|
Yes, but if v has neighbors colored R, G, B, and Y, you're stuck, and
you need to go back and change the colors of some vertices other than
v. And when you do this recoloring of vertices, you may have to recolor
vertices which are 100 steps away. If you look at the proof of the 5
Color Theorem based on Kempe chains, you can see how this happens; the
Kempe chains may be very long.
Here's how to prove the 5CT theorem; suppose you want to color a planar
graph with one of five colors (A,B,C,D,E). The only problem is a vertex
of degree 5, because the neighbors of G-v might all be colored
differently. Suppose, for clarity's sake, that the neighbors of v are
a,b,c,d,e in order, and a is colored A, b is colored B, etc. You're in
a "stuck" situation, like I described above.
So let's try re-coloring some vertices; let's recolor vertex c with
color A. If c has no neighbors colored A, we win; v can be colored C,
and we have a 5-coloring of G. Otherwise, we're not in luck. Well,
let's take the neighbors of c that are colored A and recolor them C. If
none of the neighbors of the neighbors of c were originally colored A,
we win again: color c with A, color the neighbors of c with C, and we
have a proper coloring of G. Otherwise? Well, keep going ...
Eventually, this has to stop. If we look at the vertices that are
colored A or C, and of those, the ones that you can get to from c
(let's call the set of those vertices S), if a is not one of those, we
win, because we flip-flop all the colors in S and get a proper
5-coloring. Now the set S might be huge (which was what the point was).
If a is in S, then changing the colors of the vertices in S doesn't
help; c is now colored A, and a is now colored C, and the neighbors of
v still require 5 colors. That's another story though, as this e-mail
is getting _way_ too long to digest all at once. (Another reason why I
want you to go through it carefully.)
| 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 .
That's not the point. I'm trying to reinforce the point that you cannot
just consider local vertices when determining how a vertex v is
colored; the coloring depends on the entire graph.
See above.
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.
No I'm not. In both cases, G is a "large" graph, v is a vertex, and P
consists of the neighbors of v.
I'm trying to reinforce the point that you cannot just consider local
vertices when determining how a vertex v is colored; the coloring
depends on the entire graph.
Same response.
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?
You never managed to finish the proof. You probably made some sort of
assumption which doesn't follow logically from what you already had.
I made three logical assumptions;
1. If G is not 4-colorable, then G-v is 4-colorable..
|
True. (This is from the definition of a minimal counterexample.)
| Quote: | 2. If G-v is maximized, it may not be 4-colorable.
|
"Maximized" means "maximum planar" here, or "triangulated". However,
(2) is NOT true. If G is a minimal counterexample, then G-v, even with
edges added, is 4-colorable (provided you still have a planar graph, of
course).
| Quote: | 3 If P+2e is 3-colorable, then G is 4-colorable.
|
(3) cannot be assumed. As I mentioned above, in order to 4-color G, you
may have to change the colors of some vertices which are already
colored. (This is one reason why there are research papers in the
literature with results like: "G is 4-colorable. Furthermore, you can
color S (a certain set of vertices) and get a 4-coloring of G which
agrees with the one on S." This avoids the nagging question of whether
(3) is true; it's proven explicitly.)
| Quote: | To finish the proof, I would need to analyze what happens when G-v is
maximized; ie, graph H. Perhaps, H and P+2e are always 4-colorable.
|
Since H has fewer vertices than G, they will be.
| Quote: | Then the proof has failed But perhaps sometimes P+2e is 3-colorable.
We cannot arbitrarily rule out the possibility that P+2e may sometimes
be 3-colorable.
|
If it's 3-colorable, it's 4-colorable.
| Quote: | The proof succeeds is P+2e is either not 4-colorable or is 3-colorable.
The proof fails if P+2e is 4-colorable but not 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.
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 contradicts the assumption that G was a minimal counterexample.
You sly dog, you! You were 'putting me on" all this time!
This is a standard proof by contradiction: Assume a statement is true,
get a contradiction, then deduce that the statement is really false.
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.)
It is very easy! All you have to do is prove than event with zero probability
is not 100% probable.
Well, (1) if you can use probability in this context, and (2) you can
show the event has zero probability with 100% probability, then you
can. But I doubt it's "very easy".
It's not!
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.
Do you believe in magic?
"Magic" is parlor tricks. "Magick" might be something else.
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).
(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.
The coloring of H is the same as the coloring of G-v, since every vertex in H
is also in G-v; and every vertex in G-v is also in H.
There still isn't a contradiction yet. You know (1) G is 5-chromatic,
(2) G-v is 4-colorable, and (3) H is 4-colorable. You need to show that
H can also be shown to be not 4-colorable, or that you can construct a
4-coloring of G from the one of H, to get a contradiction.
But if the new coloring (of H) is like I stated above (a,b,c,d,e, might
be colored A,B,C,D,B, in that order), then v still needs a fifth color.
And adding the edge ad or ce to H (to get H') won't help, because
you'll still have a 4-coloring of H'.
Maybe, maybe not? That's what we are going to try to find out!
|
Come on; you only have to check out two possibilities here. It'll take
fifteen seconds on a piece of paper. Draw P+ac, label the vertices,
label them with their colors, and notice that a and d have different
colors, and c and e have different colors. End of exercise. 8-)
| Quote: | 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.
I have done all the exercises, but I still do not understand why relabelling vertices
is relevant?
It shows when you can use symmetry, and when you cannot use symmetry.
Let's play a game. Stipulate a specific fixed configaration of G-v, which
generates a specific 4-coloring of P, say ABACD to start This is not
necessarily the only specific 4-coloring applicable to P, its only a
start. .
1. . I play my first chord.
2. You counter by 4-coloring P
3 I play my second chord.
Which cannot cross any other chords, of course!
4. You counter.
5. I move one of my chords
6 You counter ...
7... I move, then you counter until I can't move or you can't
counter!
I play: Chord v_1 to v_3
Your counter?
I don't have to actually be around to play. Here's my strategy:
(*) If you have a chord from v_i to v_j, and possibly one from v_i to v_k, where
j-i = 2 (mod 5) (and k-i = 3 (mod 5) if there is a chord from v_i to v_k), then
color i+1 and i-1 (mod 5) with B, and color the other three vertices
with A, C, and D (one color for each vertex; which vertex receives
which color doesn't matter).
So, for instance your move is v_1 to v_3. That means i=1 and j=3 in my
strategy, and there is no k to worry about. So I will color
i+1 and i-1 with B; that is, v_2 and v_5 are colored B.
and the other 3 vertices are colored A, C, and D, so maybe v_1 is
colored A, v_3 is colored C, and v_4 is colored D.
Very clever! I expected you to just change the colors of a or b. Now I can't add
my second chord between b & e, without removing the first.
|
Clearly, if you're allowed to add arbitrary chords, you'd win, because
you could add the edges ac, ad, bd, be, ce, and end up with a
5-chromatic graph.
| Quote: | I am tempted to challenge your move as an illegal move.
|
Why? I 4-colored P, as you asked. (Of course, if you change the rule
about what types of colorings I can do, I might possibly lose.)
| Quote: | But suppose it was legal?
|
I think you mean "But suppose it was _illegal_?"
| Quote: | Position 1. ABACD
Position 2 ABCDB
You cant change v_3 from A to C because v_4 is C
You cant change v_4 from C to D because v_5 is D
You cant change v_5 from D to B because that would make P+2e
3-colorable.
I WIN!
|
But not the game you set up the rules for. You can't say you won at
chess when you actually played checkers.
--- 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: Thu Jul 20, 2006 5:39 pm Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
icahit@gmail.com wrote:
I must be careful when I give an answer to your question. Yes my proof
has not yet published but I think it has been passed through extensive
public review in the last two years. I have given several seminars in
the mathematical departments. The bottom line is that, no one yet and
I trust, no one will be given serious comments against its correctness.
I have my doubts, especially in Cahit's paper which "settles"
Steinberg's Conjecture. In particular, I derived the conditions under
which a "triangulated ring" is 3-colorable, and they do not match
Cahit's. That, and my increased workload during the academic year, have
kept me from looking at more of the problem.
What is "Steinberg's Conjecture"? What is a "triangulated ring"?
Steinberg's conjecture states that a planar graph without any cycles of
length 4 or 5 can be 3-colored
Amateur's Proof of the SC: Every planar graph that is not 3-colorable has
at least one vertex that is the hub of an even-order wheel graph!
I assume by "even order" you mean an even number of vertices (and the
central vertex thus has odd degree). If so, you have made a classic
mistake: Confusing "P implies Q" with "Q implies P" ("Affirming the
Consequent").
|
Let "P" be a wheel graph with an odd number of spokes"
Let "Q" be '4-colorable'
Then if a graph is 4-colorable. it does not necessarily have an
odd-spoked
wheel? Do you have an image of such a graph?
| Quote: |
Such a graph must have a cycle of length 4 or 5. The graph with four
mutually adjacent vertices provides the cycle of length 4. The wheel graph
with 5 or more spokes provides the cycle of length 5.
Another reason that this "proof" is wrong is that it also shows that
any planar graphs without 4-cycles is 3-colorable. (Two triangles that
share an edge provide a 4-cycle on their own.) And this is simply
wrong; there is a planar graph with no 4-cycles which is not
3-colorable.
|
I misinterpeted the conjecture: I thought it meant;
1) a graph without a cycle of length 4 is 3-colorable; and
2) a graph without a cycle of length 5 is 3-colorable.
And of course, there is a graph without a cycle of length 5 that is
not
3-colorable. So both 4-length and 5-length cycles must be absent?
---Bill J
| Quote: | I can't seem to find an image of this last one, so I'll sketch one and
post the URL.
--- Christopher Heckman
"Triangulated ring" is a term invented by Cahit. It refers to a cycle
of length n, surrounded by triangular faces (whose 3rd vertex points
away from the cycle), then by triangular faces which point "towards"
the cycle, and then you have a cycle on the outside.
It is my opinion that the proofs should be worked out in more detail.
It is true that in the final publisheable form I will have to add a few
things and delete some unneccessary figures and explain my spiral-chain
coloring algorithm in more detail, that is three-coloring of the spiral
segments and additional stuff on three-plus-one spiral chain coloring
and also adding may be a new section for the three-edge coloring of
(bridgeless) cubic planar graphs. I will going to present my proof in
the ICM2006, Madrid in August (
http://icm2006.org/v_f/web_UC.php?CodiSeccio=14&CodiTipusEvent=4sc&Ordenacio=ae&Format=UC4sc)
and based on the feedback I receive I am going to submit to a proper
journal. The only thing that I would say about Dharwadker's "proof" of
the 4CT is that there is no description of an coloring algorithm in his
proof.
Cahit
a.khanm@gmail.com wrote:
What became of your proof of the four colour theorem? Usually people
tend to make the same old mistakes in proving the elusive theorem. Have
you found any errors yet or do you still think that your proof is
correct? Another person by the name of Ashay Dharwadker has claimed to
have proven the four colour theorem but his proof never made it to a
journal. What is the current status of your proof?
icahit@gmail.com wrote:
May be the answer to Bill's question is in my response in another group
at
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1150590683
Cahit
Proginoskes 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.
But a variation of induction is the backbone to reduction, a technique
that both Appel and Haken, and Robertson Sanders Seymour Thomas used to
find a proof.
--- Christopher Heckman |
|
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Thu Jul 20, 2006 10:52 pm 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:
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.
Then you missed the point of the exercise.
Obviously! What is the point?
Destroying symmetry means the number of cases increases.
How does this apply directly to the proof? |
| 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!
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.
And you have thus done all 5 cases. I rest my case.
Or I could relabel the vertices so that a & c always have the same
color!
In this case, you're taking advantage of symmetry. I rest my case.
I still do not understand why I need to account for destroying the
symmetry?
Because not all 4-colorings of P+ac are equal. If you have two
4-colorings of P, you can use symmetry operations and color shuffling
to turn one into the other. If you have two 4-colorings of P+ac, this
is not necessarily the case. You cannot turn one type of coloring of
P+ac below into the other.
Try it.
Why would I want to? A 4-coloring is a 4-coloring. |
| 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!
No. In order to see whether G is 4-colorable, you need to color ALL of
G, not just a piece of it. It may happen that you need to have 4
different colors on P+2e in order to color G. (This is called
"extending a coloring" from one graph to another.) Remember, the only
coloring you have for the entire graph requires P+2e to be colored with
5 colors.
By definition, G is 4-colorable if P is 3-colorable. This is a basic premise of the
proof.
No; that only applies to P and the central vertex v. You may need a
fifth color to color the rest of G. You have the burdon of proof, i.e.,
you have to show that this is not the case.
P is a subgraph of G-v, which in turn is a subgraph of G. If G-v is |
4-colorable
when P is 3-colorable, how can G not be 4-colorable?
| Quote: | *I do not have a coloring (per se) for the entire graph!.
Then you haven't proven the 4CT. You have the burdon of proof, by
stating that you have proved it. This means that you need to be able to
handle any relevant questions that I may ask. Such as: "How can you
guarantee that the _whole graph_ is 4-colored, not just P and its
neighbors?"
|
I have never stated that I have proven anything! I cannot guarantee
that the
_whole graph_ is 4-colorable! What I hope to do is to show that IF the
whole graph is not 4-colorable, then there is a smaller graph that is
also
not 4-colorable!
| Quote: |
I merely present a
scenario in which the proper coloring is in doubt; and ask you to choose
the proper coloring!*
That is my role in the situation.
Again, that was the point of one of the exercises.
Again, I missed the point!
Then you need to go back and re-read this post, including everything
that has been mentioned previously. I finding myself repetitiously
repeating myself over and over again in this thread.
I seem to have the same problem. |
| 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?
The only symmetry that P+ac has is the "reflective" one mentioned right
before the exercies.
A symmetry ("isomorphism") is properly defined as a bijective map f
from {a,b,c,d,e} to {a,b,c,d,e} such that (x,y) is an edge exactly when
(f(x),f(y)) is. The only symmetries that the graph P+ac has are the
functions defined by:
(i) f(a) = a, f(b) = b, f(c) = c, f(d) = d, f(e) = e, OR
(ii) f(a) = c, f(b) = b, f(c) = a, f(d) = e, f(e) = d.
Here's how you get started: A symmetry preserves degrees, so x and f(x)
have the same degree, for all x.
Look at the vertices of degree 3. The vertices of degree 3 are a and c,
so either
(i') f(a) = a and f(c) = c, OR
(ii') f(a) = c and f(c) = a.
Then b is a vertex adjacent to a and c, so f(b) must be adjacent to
f(a) and f(c), i.e., f(b) is adjacent to a and c (regardless of whether
we are in case (i') or (ii')). Now b is the ONLY vertex with this
property, so you must have
f(b) = b. Then you can continue and establish that the two functions
listed in (i) and (ii) above are the only ones with the symmetry
property.
wthdic? How does this effect the coloring?
I don't know what you mean by "this", but I'll assume it's the symmetry
(isomorphism) above.
The whole point of the symmetry discussion is that, given any two
colorings of P, you can transform one into the other by doing the
following, a finite number of times:
(a) a "rotation" (relabel the vertices so that old a = new b, old b =
new c, etc), OR
(b) swapping two color names.
For instance, if you start off with the coloring
x(a) = A, x(b) = B, x(c) = C, x(d) = D, x(e) = B,
you can transform it into the coloring
x(a) = B, x(b) = C, x(c) = D, x(d) = C, x(e) = A.
using the operations above.
Here's how:
x(a) = A, x(b) = B, x(c) = C, x(d) = D, x(e) = B [first coloring]
x(a) = A, x(b) = C, x(c) = B, x(d) = D, x(e) = C [swap colors B and C]
x(a) = C, x(b) = A, x(c) = C, x(d) = B, x(e) = D [rotate]
x(a) = D, x(b) = C, x(c) = A, x(d) = C, x(e) = B [rotate]
x(a) = A, x(b) = C, x(c) = D, x(d) = C, x(e) = B [swap colors A and D]
x(a) = B, x(b) = C, x(c) = D, x(d) = C, x(e) = A [swap colors A and B]
and we get the second coloring.
You _cannot_ do this when P is replaced by the graph P+ac.
For the umpteenth time, why should want to or need to find a second |
coloring
for P + ac?
| Quote: | Why should I keep "b" labelled as "b"?
It has to be. (Sorry about the pun.)
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?
Here I'm talking about the whole graph being a cycle. And I'm trying to
reinforce the point that you cannot just consider local vertices when
determining how a vertex v is colored; the coloring depends on the
entire graph.
Yes and no. The coloring of v depends solely upon the colors of its neighbors;
which in turn depends upon the coloring of the entire graph. For instance, if
v has only R, G, & B neighbors, nothing in the rest of the graph can force
v not to be Y In that sense the color of v does not depend on the coloring
of the rest of the graph.
Yes, but if v has neighbors colored R, G, B, and Y, you're stuck,
|
Not really! Remember that v has 5 neighbors. When v is removed, the
colors
of its former neighbors do not change; at least they shouldn't?. Two
of v's 5
neighbors must be the same color; say vertices a & c. When I stick a
chord between a & c; then the neighbors of v; ie graph P; are not
properly
4-colored unless either a or c can be recolored. If you can't
properly 4-color
P, I am content. If you can, I just move my chord to where it will be
the
most inconvenient.
In the game I suggested, I envisioned an endless cycle of recoloring &
chord
relocation. This would require some 30 different colorings (RGRBY is
not the
same as BGRBY, nor is YBGRB) Then I would observe that if all of
these different colorings are possible; then just maybe, the coloring
of P is absolutely independent
of the "rest of G"! Then G is 4-colorable.
If the cycle cannot be completed, then H is not 4-colorable.
.
Either way, G cannot be an mce/4CT!
| Quote: | you need to go back and change the colors of some vertices other than
v. And when you do this recoloring of vertices, you may have to recolor
vertices which are 100 steps away. If you look at the proof of the 5
Color Theorem based on Kempe chains, you can see how this happens; the
Kempe chains may be very long.
Here's how to prove the 5CT theorem; suppose you want to color a planar
graph with one of five colors (A,B,C,D,E). The only problem is a vertex
of degree 5, because the neighbors of G-v might all be colored
differently. Suppose, for clarity's sake, that the neighbors of v are
a,b,c,d,e in order, and a is colored A, b is colored B, etc. You're in
a "stuck" situation, like I described above.
So let's try re-coloring some vertices; let's recolor vertex c with
color A. If c has no neighbors colored A, we win; v can be colored C,
and we have a 5-coloring of G. Otherwise, we're not in luck. Well,
let's take the neighbors of c that are colored A and recolor them C. If
none of the neighbors of the neighbors of c were originally colored A,
we win again: color c with A, color the neighbors of c with C, and we
have a proper coloring of G. Otherwise? Well, keep going ...
Eventually, this has to stop. If we look at the vertices that are
colored A or C, and of those, the ones that you can get to from c
(let's call the set of those vertices S), if a is not one of those, we
win, because we flip-flop all the colors in S and get a proper
5-coloring. Now the set S might be huge (which was what the point was).
If a is in S, then changing the colors of the vertices in S doesn't
help; c is now colored A, and a is now colored C, and the neighbors of
v still require 5 colors. That's another story though, as this e-mail
is getting _way_ too long to digest all at once. (Another reason why I
want you to go through it carefully.)
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 .
That's not the point. I'm trying to reinforce the point that you cannot
just consider local vertices when determining how a vertex v is
colored; the coloring depends on the entire graph.
See above.
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.
No I'm not. In both cases, G is a "large" graph, v is a vertex, and P
consists of the neighbors of v.
I'm trying to reinforce the point that you cannot just consider local
vertices when determining how a vertex v is colored; the coloring
depends on the entire graph.
Same response.
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?
You never managed to finish the proof. You probably made some sort of
assumption which doesn't follow logically from what you already had.
I made three logical assumptions;
1. If G is not 4-colorable, then G-v is 4-colorable..
True. (This is from the definition of a minimal counterexample.)
2. If G-v is maximized, it may not be 4-colorable.
"Maximized" means "maximum planar" here, or "triangulated". However,
(2) is NOT true. If G is a minimal counterexample, then G-v, even with
edges added, is 4-colorable (provided you still have a planar graph, of
course).
|
You are disallowing the case where G is not 4-colorable and not
minimal.
You are saying that if Chi(G) = 5, then G is minimal! This is not
axiomatic!
| Quote: |
3 If P+2e is 3-colorable, then G is 4-colorable.
(3) cannot be assumed. As I mentioned above, in order to 4-color G, you
may have to change the colors of some vertices which are already
colored.
|
We are assuming that G-v is 4-colorable; aren't we? If G-v is not
4-colorable;
then G is not minimal. If G-v IS 4-colorable, then the only way to
make
G not 4-colorable is if P is not 3-colorable! Indisputable fact!
(This is one reason why there are research papers in the
| Quote: | literature with results like: "G is 4-colorable. Furthermore, you can
color S (a certain set of vertices) and get a 4-coloring of G which
agrees with the one on S." This avoids the nagging question of whether
(3) is true; it's proven explicitly.)
To finish the proof, I would need to analyze what happens when G-v is
maximized; ie, graph H. Perhaps, H and P+2e are always 4-colorable.
Since H has fewer vertices than G, they will be.
|
Again assuming that if Chi(G) = 5, then G is minimal!
| Quote: |
Then the proof has failed But perhaps sometimes P+2e is 3-colorable.
We cannot arbitrarily rule out the possibility that P+2e may sometimes
be 3-colorable.
If it's 3-colorable, it's 4-colorable.
The proof succeeds is P+2e is either not 4-colorable or is 3-colorable.
The proof fails if P+2e is 4-colorable but not 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.
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 contradicts the assumption that G was a minimal counterexample.
You sly dog, you! You were 'putting me on" all this time!
This is a standard proof by contradiction: Assume a statement is true,
get a contradiction, then deduce that the statement is really false.
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.)
It is very easy! All you have to do is prove than event with zero probability
is not 100% probable.
Well, (1) if you can use probability in this context, and (2) you can
show the event has zero probability with 100% probability, then you
can. But I doubt it's "very easy".
It's not!
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.
Do you believe in magic?
"Magic" is parlor tricks. "Magick" might be something else.
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).
(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.
The coloring of H is the same as the coloring of G-v, since every vertex in H
is also in G-v; and every vertex in G-v is also in H.
There still isn't a contradiction yet. You know (1) G is 5-chromatic,
(2) G-v is 4-colorable, and (3) H is 4-colorable. You need to show that
H can also be shown to be not 4-colorable, or that you can construct a
4-coloring of G from the one of H, to get a contradiction.
But if the new coloring (of H) is like I stated above (a,b,c,d,e, might
be colored A,B,C,D,B, in that order), then v still needs a fifth color.
And adding the edge ad or ce to H (to get H') won't help, because
you'll still have a 4-coloring of H'.
Maybe, maybe not? That's what we are going to try to find out!
Come on; you only have to check out two possibilities here. It'll take
fifteen seconds on a piece of paper. Draw P+ac, label the vertices,
label them with their colors, and notice that a and d have different
colors, and c and e have different colors. End of exercise. 8-)
|
| Quote: | 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.
I have done all the exercises, but I still do not understand why relabelling vertices
is relevant?
It shows when you can use symmetry, and when you cannot use symmetry.
Let's play a game. Stipulate a specific fixed configaration of G-v, which
generates a specific 4-coloring of P, say ABACD to start This is not
necessarily the only specific 4-coloring applicable to P, its only a
start. .
1. . I play my first chord.
2. You counter by 4-coloring P
3 I play my second chord.
Which cannot cross any other chords, of course!
4. You counter.
5. I move one of my chords
6 You counter ...
7... I move, then you counter until I can't move or you can't
counter!
I play: Chord v_1 to v_3
Your counter?
I don't have to actually be around to play. Here's my strategy:
(*) If you have a chord from v_i to v_j, and possibly one from v_i to v_k, where
j-i = 2 (mod 5) (and k-i = 3 (mod 5) if there is a chord from v_i to v_k), then
color i+1 and i-1 (mod 5) with B, and color the other three vertices
with A, C, and D (one color for each vertex; which vertex receives
which color doesn't matter).
So, for instance your move is v_1 to v_3. That means i=1 and j=3 in my
strategy, and there is no k to worry about. So I will color
i+1 and i-1 with B; that is, v_2 and v_5 are colored B.
and the other 3 vertices are colored A, C, and D, so maybe v_1 is
colored A, v_3 is colored C, and v_4 is colored D.
Very clever! I expected you to just change the colors of a or b. Now I can't add
my second chord between b & e, without removing the first.
Clearly, if you're allowed to add arbitrary chords, you'd win, because
you could add the edges ac, ad, bd, be, ce, and end up with a
5-chromatic graph.
|
Why can't I add arbitrary chords? Why can't I maximize G-v? What
keeps
me from adding a chord wherever I want as long as it does not cross
another
chord. Why can't I move a chord from one pair of vertices to another
if I choose?
| Quote: |
I am tempted to challenge your move as an illegal move.
Why? I 4-colored P, as you asked. (Of course, if you change the rule
about what types of colorings I can do, I might possibly lose.)
But suppose it was legal?
I think you mean "But suppose it was _illegal_?"
Position 1. ABACD
Position 2 ABCDB
You cant change v_3 from A to C because v_4 is C
You cant change v_4 from C to D because v_5 is D
You cant change v_5 from D to B because that would make P+2e
3-colorable.
I WIN!
But not the game you set up the rules for. You can't say you won at
chess when you actually played checkers.
|
I should have mentioned that you can't make P + 2e 3-colorable,
Sorry! There is a second unwritten rule. Suppose the following
positions
occurred in the course of the game:
ABACD
ABDCD
ABDCB
Then it could be argued that ABACB is also a legitimate position!.
Then
P + 2e is 3-colorable! Any combination of positions that suggests a
3-coloring
for P + 2e is possible, is not allowed!
This may be an unenforceable rule,? If it is, I hope the
counter-arguments
are positive?
---Bill
| 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 |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 1:41 am | All times are GMT
|
|
Online Advertising | News | Mortgage Calculator | Problem Mortgage | Debt Consolidation
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
