Re: The Lazy Person's Guide to Proving the Four Color Theorem
- From: "Proginoskes" <CCHeckman@xxxxxxxxx>
- Date: 18 Aug 2006 02:32:49 -0700
bill wrote:
Proginoskes wrote:
bill wrote:The colorability of P_max (P+2edges) is something that must be determined by
Let G be a simple loopless maximal planar graph.
The 4CT is false if there exists a graph G such that Chi(G) > 4 and every graph (H)
with fewer vertices than G is 4-colorable.
In fact, the 4CT is false if there is a graph G with Chi(G) > 4,
period. The extra condition, on smaller graphs, defines a minimal
counterexample.
If such a graph G exists it is called a
minimal counterexample (mce) to the 4CT.
The 4CT can be proven by proving that no mce can exist.
Some parameters of G have already been established. One of these conditions is that
G cannot have any vertices of degree less that 5. Since G is maximal planar, it must
have at least one vertex of degree = 5. If that vertex (v) is removed from G, the resulting
graph is (G-v).
Let's assume that Chi(G) > 4. If G is an mce, (G-v) must be 4-colorable. Now here
is a very critical point;
For every possible 4-coloring of (G-v), there can be no proper
4-colorings of G.
Correct, since we assumed that Chi(G) > 4.
The five vertices that are/were the neighbors of v form a pentagon (P). P is the
interface between (G-v) and G. To assure that Chi(G) > 4 when Chi(G-v) =4
it is necessary that P cannot be 3-colored!
Not exactly. It is necessary that no 3-coloring of P extends to the
rest of G, or equivalently, if C is a coloring of G, then C(P) has four
colors.
P (by itself) certainly can be 3-colored. (BTW, it is not too difficult
to show that every triangle in a mce must be facial, so P really is a
pentagon; there are no extra edges in P (as a subgraph of G).)
Second critical point;
Graph (G-v) is not maximum (maximal) planar. It is lacks two edges. (G-v)
can be maximized by the addition of any two legal edges. These edges will be added
as internal chords to graph P. When (G-v) is maximized we can call it graph H.
H has fewer vertices than G. If H is not 4-colorable, then G is not minimal and
therefore, not an mce.
If, after the addition of the maximizing edges, graph P cannot be properly 4-colored,
then H cannot be properly 4-colored.
True. However, P+2edges _can_ be properly 4-colored; in fact
Chi(P+2edges) = 3! So your statement is "vacuously" true; it's a
statement of the form
False -> Something, which is always true.
logical analysis.
It's proven using the method of "Sitting Down And Doing It". When you
have a graph with lots of triangles in it, it doesn't take much work to
determine whether it's 3-colorable.
Not by decree! The colorability of P_max is determined by
the status of G and in-turn reflects the status of G.
If Chi(P_max) > 4, then G is not minimal
If Chi(P_max) = 4, then G is an mce
If Chi(P_max) < 4, then G is 4-colorablel
And once again you've confused the issue of coloring *just P_max* and
coloring *P_max plus the rest of G-v*.
Although maybe by P_max, you don't mean P+2edges, but the graph G-v
with two edges added. Remember, P was just the neighbors of v, which is
a pentagon. A 4-coloring of G-v (plus two edges) exists by the
assumption that G is a mce; certainly G-v (plus two edges) has fewer
vertices than G.
A statement about extending colorings from P to the rest of G-v doesn'tThe first ME (maximizing edge) goes between vertices that have the
help, either, since one of the proper 4-colorings of P+2edges might
extend to a 4-coloring of G-v. For this to be a real proof, this
possiblity must be taken care of.
same color. This means that P is cannot be properly colored unless one
of
(If you are using Google Groups to post to Usenet, don't both pressing
ENTER until you get to the end of a paragraph. GG automatically inserts
a carriage return after a certain number of letters, unless the line
begins with ">". If you type a few more, then you get "relics" like the
last two lines above, where "of" appears on a line by itself. I have
been fixing this in my replies.)
these vertices is recolored. If neither vertex can be recolored R, G, B or Y,
then Chi(P_max) > 4!
But since the vertices of P_max _can_ be recolored in one of four
colors, this isn't an issue. It's like saying that if the sun was green
yesterday, then George W. Bush will be teaching at Harvard this fall.
Since the first part is false, the second part is irrelevant.
The second ME [maximizing edges] determines which vertex to recolor.
Here's a simple example:
v_a = R; v_b = G; v_c = R; v_d = B & v_e = Y. The ME's are {ac} and {ce}
Obviouisly v_c cannot be recolored G, B or Y; unless v_b or v_d or v_e
are also recolored in some way. To keep it simple to start, lets stipulate that
for the moment, only v_a can be recolored.
Recolored in what context? You are omitting a very important detail
here. If you are only worried about coloring P+ac+ce, then you only
need 3 colors, and there are several ways to do that. If you are
worried about coloring G-v+ac+ce (which you should be), then the
coloring of P needs to match up with the rest of the coloring of G.
If you are going for the latter, then this is a very restrictive way to
do it.
To achieve 4-colorability, v_a would have to be recolored "B" [assuming that
no other vertices are also recolored]
****If v_a can be recolored 'B', it could have been colored B in the first place!****
.... and you get a 4-coloring of G after using Kempe chains (thus ending
the proof).
The possibility that v_a could have originally been either B or R is conceded!
No, that just means we need to change colors on vertices *other than
v_a*; maybe on v_b, v_c, and v_e, for instance.
You assumed we can recolor just v_a (and extend that coloring to G);
you got a contradiction, so the assumption is wrong; hence we cannot
just recolor v_a: there is more that needs to be done.
Now we go back to the start and assign the ME's to {ac} and {ad}. Now v_c
is the vertex to recolor and the only alternate color is 'Y' The conclusion that
v_c could have originally been colored Y is "self-evident"!
From this I infer that the original coloring of P could have and should
have been;
v_a = B; v_b = G; v_c = Y; v_d = B & v_e = Y.
If this is true, then Chi(G) < 5.
Once again, the contradiction shows ONLY that you need to color MORE
THAN one vertex.
But I suspect that you are not ready to accept this conclusion! So we tacitly
agree on a new coloring of P, say v_a = B; v_b = G; v_c = R ; v_d = B & v_e = Y.
Now, ME pairs {ac}/ {ad} and {ad}/ {bd} are invoked. This leads to a third
coloring for P.
There's nothing that states that a coloring *only* of P will give you a
coloring of *all of* G-v.
A new coloring for P demands a new set of ME's, etc.
If this process in carried to its conclusion; it will become apparent that this is
possible if and only if, every one of the 240 distinguishable 4-colorings for P
can be extended to a proper 5-coloring of a given G. [...]
You've got the order of graph/coloring mixed up here. You are showing
that one particular coloring doesn't work for G-v+2 ME's; that does not
mean that none of the colorings will work.
Once again, I have stated this repeatedly in "the other thread".
To be proven: P is 4-colorable if and only if Chi(G) < 5.
We know that Chi(G) > 4,
***We DO NOT "KNOW" that Chi(G) > 4!***
If G is a counterexample, then it is. And this statement was in that
context (which you have obliterated).
so "Chi(G) < 5" is false. Hence you are trying
to show that P is not 4-colorable, which is blatantly impossible, in
light of what I explained above.
I am sure that I meant P_max, since P is 4-colorable if and only if Chi(G) > 4.
If P is the pentagon, then the 4-colorability of P has nothing to do
with the chromatic number of another graph.
If Chi(P_max) = 4 and Chi(G) = 5, then the 4CT is false.
If Chi(P_max) = 4 --- we already are assuming that Chi(G) = 5 --- then
you cannot conclude that the 4CT is false. Not having a proof that the
4CT is true is NOT the same as having a proof that the 4CT is not true.
This is like saying that: If I can't show that it will rain tomorrow,
then I can show that it won't rain.
So in that context, it is essential to prove that Chi(G) < 5 if Chi(P-max) = 4.
This is what I've meant by "extending" colorings.
Offhand, I do not see any way of proving this.
Neither does anyone else on the planet. 8-) Especially if you don't
look past the neighbors of one particular vertex.
So it may be necessary to prove that if
P_max is 4-colorable, it is also 3-colorable.
But you still need to show that Chi(G) < 5 in this case.
Another way is to insist that v_a cannot be recolored from R to B unless a
viable algorithm is developed. Or if it is conceded that v-a CAN be
recolored R to B and v_c CAN be recolored R to Y; that reasons why
both cannot be simultaneously
recolored must be explained in advance.
It is very easy to choose the maximizing edges so that P is not
properly 4-colored.
And I bring up what I've said many times before: You can do this so
that a particular coloring C of P+2e is no longer properly colored, but
there can be other colorings out there where P+(these two edges) _will_
be properly 4-colored.
So I move the edges! I can move the edges as indiscriminately as I
choose.
But no matter how you move the edges, there might be a 4-coloring of
G-v. (And, if G is a mce, then there MUST be one.)
--- Christopher Heckman
Now, proof of the 4CT depends entirely upon proving that P cannot be properly
4-colored. Or that if P can be properly 4-colored, then G can also be properly 4-colored.
Neither of which has been shown. Thus this is not a proof.
It is not supposed to be a completed proof. Just an introduction!
.
- Follow-Ups:
- References:
- Prev by Date: Re: What are the most popular research themes?
- Next by Date: Re: JSH: Measuring post impact
- Previous by thread: Re: The Lazy Person's Guide to Proving the Four Color Theorem
- Next by thread: Re: The Lazy Person's Guide to Proving the Four Color Theorem
- Index(es):
Relevant Pages
|
