Re: Proof of the Four Color Theorem by Contradiction
- From: tjensen@xxxxxxxxxxxxx
- Date: Wed, 29 Oct 2008 11:00:40 -0700 (PDT)
On Oct 16, 7:38 pm, bill <b92...@xxxxxxxxx> wrote:
I will try to rethink my assessment of the proof
IMMHO, it begins by assuming that there is a set of
configurations such that at least one configuration appears in every
planargraph. Then it proves that nographwith at least
one of those configurations can be an MCE.
Now I can see that proving that an MCE cannot have one
of a set of configurations might be considered a proof by
contradiction.
Bill J
I am not convinced that this is proof by contradiction.
I can agree with you in this lack of conviction. You
already have links to references from amzoti, so you may
go and check for yourself whether the following is not an
accurate interpretation of both computer assisted proofs.
How to prove 4ct? Both proofs use the same method.
You show that every plane graph contains at least one
member of some particular set of small plane graphs as a
kind of subgraph. This set of small graphs is called "the
set of unavoidable configurations." (Actually in the first
proof by Appel and Haken and Koch, the members of this set
were not shown to appear as actual subgraphs, but rather
to appear as "immersions", a slightly more general concept,
but this is largely a technicality). The proof of the
existence of such a kind of subgraph in any plane graph is
at any rate quite direct. You are told about an algorithm,
which is an application of the Euler formula for plane
graphs, to look for and exhibit an instance of such a
graph within any input plane graph, no matter which one is
given to you.
Now you have more to work with. In the plane graph
which you are interested in 4-coloring, you now have some
subgraph from the unavoidable set staring you in the face.
Both proofs now do the following to that subgraph. They
squeeze it down to some smaller size, possibly by removing
it entirely, but typically not anything that drastic. Then
you have a smaller graph. And this is where it is convenient
to "pretend" that the proof is a "proof by contradiction."
Because now it is easy to state briefly that, by virtue of
being smaller than the original graph, and by the assumption
that the original graph was assumed to be a smallest
counterexample, the smaller graph allows a 4-coloring. So
you assume that there exists some 4-coloring of the smaller
graph, which means that you now have even more to work with,
in addition to the original input graph, you have a
particular kind of identified small subgraph, and you have
already a 4-coloring of the graph you get by squeezing down
this subgraph to something smaller in a certain way. Both
proofs now continue by showing that there is a way to
change this 4-coloring of the smaller graph so that you
achieve a 4-coloring of the original graph. Which is a
contradiction if you assumed that the original graph was a
smallest counterexample. But actually if you did not assume
anything about the original graph, other than it was a plane
graph, then it is not a contradicton, since now you actually
are in possession of a 4-coloring of this graph, by
construction. Though the construction is admittedly recursive,
since the smaller graph, for which in the proof by smallest
counterexample you can assume 4-colorable, you have to cycle
it back into the algorithm to get a subgraph from the
unavoidable set which you squeeze down to get a smaller graph
which you again search for an unavoidable configuration etc.
until you reach a base case which is trivially 4-colorable
and you proceed to blow things up again to construct the
colorings of your larger graphs.
The major improvement by the newer proof by Robertson,
Sanders, Seymour and Thomas as compared with the old proof
is that their algorithm for 4-coloring a plane graph runs
much faster than the algorithm which you can recover from
the old proof. The actual historical improvement of the
algorithm was 2-step: the first proof of 4ct meant a very
slow algorithm for constructing a 4-coloring. In 1989 the
authors of the proof, Ken Appel and Wolfgang Haken wrote a
thick book to explain how a modified version of the proof
may 4-color any plane graph rather quickly, in time O(n^4)
for plane graphs with n nodes. The RSST proof improves
this complexity to O(n^2). That may not be the last word
on the complexity of plane graph 4-coloring yet.
Cheers, kluto
.
- Follow-Ups:
- Re: Proof of the Four Color Theorem by Contradiction
- From: spudnik
- Re: Proof of the Four Color Theorem by Contradiction
- References:
- Proof of the Four Color Theorem by Contradiction
- From: bill
- Re: Proof of the Four Color Theorem by Contradiction
- From: Arturo Magidin
- Re: Proof of the Four Color Theorem by Contradiction
- From: bill
- Re: Proof of the Four Color Theorem by Contradiction
- From: amzoti
- Re: Proof of the Four Color Theorem by Contradiction
- From: bill
- Re: Proof of the Four Color Theorem by Contradiction
- From: Mariano Suárez-Alvarez
- Re: Proof of the Four Color Theorem by Contradiction
- From: bill
- Proof of the Four Color Theorem by Contradiction
- Prev by Date: Re: Math and the beginning of a a concept bigger than the universe
- Next by Date: Need hands on activity regarding knot theory
- Previous by thread: Re: Proof of the Four Color Theorem by Contradiction
- Next by thread: Re: Proof of the Four Color Theorem by Contradiction
- Index(es):
Relevant Pages
|
