the four color theorem...

[noemata]

First, I have to say that I'm not a mathematician. Maybe that's why I
don't understand why the four color theorem has been so difficult to
prove.
The theorem states that no more than four colors are necessary to
color
the regions of any map to separate them.
My understanding goes like this:
First you try to draw a counterexample. Then you realize it's
impossible. And then you realize why: All the regions have to touch
all
other regions - three goes fine, the fourth has to surround at least
one
of them which in turn frees its color for reuse.
This problem seems to translate nicely into graph theory where the
colors are dots and their contacts are lines between. Given this, it's
possible to draw a graph with 1, 2, 3 and 4 dots with lines connecting
all-to-all without any line crossing each other. If you try to add a
5.
dot, its connecting lines will have to cross an existing line; so,
it's
not possible to draw a graph with five dots without any line crossing
another line. See image:
Loading Image...
This seems trivial, so why has the theorem been difficult to prove?
Restating the theorem as: It is impossible to draw a two-dimensional
map
where five or more colors are necessary, it then seems intuitively
true
via graph theory. Now the problem might still exist, in the word
"necessary" - who knows?
For me this is proof enough. On the other hand my ideas are often
crank... But what's wrong?

[Hero]

Post by noemata
First, I have to say that I'm not a mathematician. Maybe that's why I
don't understand why the four color theorem has been so difficult to
prove.
The theorem states that no more than four colors are necessary to
color
the regions of any map to separate them.
First you try to draw a counterexample. Then you realize it's
impossible. And then you realize why: All the regions have to touch
all
other regions - three goes fine, the fourth has to surround at least
one
of them which in turn frees its color for reuse.
This problem
seems
to translate nicely into graph theory where the
colors are dots and their contacts are lines between. Given this, it's
possible to draw a graph with 1, 2, 3 and 4 dots with lines connecting
all-to-all without any line crossing each other. If you try to add a
5.
dot, its connecting lines will have to cross an existing line; so,
it's
not possible to draw a graph with five dots without any line crossing
another line. See image:http://noemata.net/ontheball/graph-4-color-theorem.png
This seems trivial, so why has the theorem been difficult to prove?
Restating the theorem as: It is impossible to draw a two-dimensional
map
where five or more colors are necessary, it then seems intuitively
true
via graph theory. Now the problem might still exist, in the word
"necessary" - who knows?
For me this is proof enough. On the other hand my ideas are often
crank... But what's wrong?

It seems...
but You see, someone has a drawing with 273 points arranged in a
special
manner and in this there are 6 points which connect directly, without
crossing.
You might not believe and want to see this drawing.
No - it's up to You, to show that this drawing does not exist. So
You need some fantasy to explain this or hard work in drawing all
possible graphs of 273 points - if You want to prove, and not just
believe Your intuiton.
And to be honest, points are no coloured areas. So if there is a
structural identy between a coloured map and line-connected
points, this is not total, it's also differing in some respects.
You must show as well, that for this problem the identy in
structur exists.

With friendly greetings
Hero

[spudnik]

the "mapping" from polygons (countries)
to vertices is a simple, dual relationship, and
it has been used on 4CT since the beginning,
probably to save coloring costs in printing.

Post by Hero
And to be honest, points are no coloured areas. So if there is a
structural identy between a coloured map and line-connected
points, this is not total, it's also differing in some respects.

thus:
on the wayside,
directly proportional means, not inversely proportional,
as in the "inverse second-power law" that Hooke derived
from Kepler's orbital constraints (and,
it has nothing in particular to do with "skwares" .-)

thus:
the M-set's property of "universality" or self-
similarity -- the mini-bugs like the big cardioid --
is strictly an artifact of the floating-point spec (and
its many implimentations); however, monsieur M. could
only beg the question, over ten years ago, because
he never bothered to speak with the engineers
at his IBM fellowship. (he had not gotten any
further, when he came to campus & spoke, again,
couple o'years ago .-)

Post by Hero
http://arxiv.org/PS_cache/hep-ph/pdf/0112/0112317v1.pdf
Fractals are usually build with complex numbers, like the Mandelbrodt

thus:
yeah, but what is the integer, Avagadro's number?...
do you know the surfer's value of pi?

thus:
well, that is where the problem with assigning a particle
to a wave, a la de Broglie et al, comes. the assumption,
that causes folks to say "particle," is that because a quantum
(wave) of light is absorbed by one atom of siver dioxide (say,
in the photographic emulsion; or, other detector) --some how--
that it must be that a rock of light hit the electronic orbital
(although
this is never specified, as to how it could be, and the whole problem
of EM is also hard to describe, and is confounded
with the absurd notion of the "plane wave").
this is really all of a confusion from Newton's "geometrical
optics,"
that is, the "ray" of light, which is just one "normal"
to the wave (or Huyghens wavelet).

Post by Hero
You assume the particle exits both slits because you assume the
particle creates the interference pattern in and of itself.

thus:
about your five "cloture" events, the real problem is that
"the Fed" was never properly ratified (and is unconstitutional
for that reason, if not directly; it is modeled upon the Federal
Reserve System
of England). of coursel the 527 cmtes. have essentially taken
over the TV advertizing on all national issues & candidates,
through an Act that was passed unaanimously in both houses.

Post by Hero
"Senate rules don't trump the Constitution" --http://GreaterVoice.org/60

thus:
I've been saying, for a while, that if "green" gasoline can
be made, and gasoline fuel cells, what is the problem
with Fossilized Fuels (TM), which ain't fossilized? ... anyway,
see "Green Freedom" in the article,
which is not quite what I was refering to!

Post by Hero
Thorium has other interesting features. For example, in
oxide form as would probably be used, Thorium has a
higher thermal conductivity than Uranium oxide. That
means the fuel will be cooler for any given power output.
It's got interesting mechanical properties also.
There are a number of new reactor designs being touted.
http://thorium.50webs.com/

thus:
Copenhagen's "reifiying" of the mere probabilities
of detection, is the biggest problem, whence comes
both "perfect vacuum" and "quantum foam" etc. ad vomitorium,
as well as the brain-dead "photon" of massless and
momentumless and pointy rocks o'light, perfectly aimed
at the recieving cone in your eye, like a small pizza pie.

thus:
all vacuums are good, if they suck hard enough, but
there is no absolute vacuum, either on theoretical or
Copenhagenskooler fuzzy math grounds.

thus:
magnetohydrodynamics is probably the way to go, yes;
not "perfect vacuum or bearings" -- and,
where did the link about YORP, include any thing
about the air-pressure?... seems to me,
it's assuming Pascal's old, perfected Plenum.
twist your mind away from the "illustrated
in _Conceptual Physics/for Dummies_" nothingness
of the massless & momentumless & pointy "photon"
of the Nobel-winning "effect" in an electronic device -- yeah,
CCDs -- the Committee's lame attempt to "save the dysappearance"
of Newton's corpuscle.
also, please don't brag about free God-am energy,
til you can demonstrate it in a perpetuum mobile!

Post by Hero
It stops because it has bad bearings. These asteroids

thus:
so, a lightmill is that thing with black & white vanes
on a spindle in a relative vacuum?
you can't rely on "rocks o'light" to impart momentum
to these vanes, only to be absorbed electromagnetically
by atoms in them; then, perhaps,
the "warm side" will have some aerodynamic/thermal effect
on the air in the bulb, compared to the cool one.
thus:
even if neutrinos don't exist,
Michelson and Morely didn't get no results!

Post by Hero
Could neutrino availability affect decay rates?

thus:
every technique has problems. like,
you can't grow hemp-for haemorrhoids under a photovoltaic,
without a good lightbulb.
the real problem is that, if Santa Monica is any indication,
the solar-subsidy bandwagon is part of the cargo-cult
from Southwest Asia (as is the compact flourescent lightbub,
the LED lightbulb etc. ad vomitorium).

Post by Hero
Government subsidies, and fat returns on PVs?

--Light: A History!
http://wlym.com

[Hero]

Post by spudnik
the "mapping" from polygons (countries)
to vertices is a simple, dual relationship, and
it has been used on 4CT since the beginning,
probably to save coloring costs in printing.

That it has been used is not revealing, that
it might deliver next time a wrong result.
You have to prove.

Post by spudnik

Post by Hero
And to be honest, points are no coloured areas. So if there is a
structural identy between a coloured map and line-connected
points, this is not total, it's also differing in some respects.

on the wayside,

...

Post by spudnik
the M-set's property of "universality" or self-

...

Post by spudnik
yeah, but what is the integer, Avagadro's number?...

.....

Post by spudnik
well, that is where the problem with assigning a particle

,,,

Post by spudnik
about your five "cloture" events, the real problem is that

.....

Post by spudnik
I've been saying, for a while, that if "green" gasoline can

.....

Post by spudnik
Copenhagen's "reifiying" of the mere probabilities

....

Post by spudnik
all vacuums are good, if they suck hard enough, but
magnetohydrodynamics is probably the way to go, yes;

...

Post by spudnik
so, a lightmill is that thing with black & white vanes

.....

Post by spudnik
even if neutrinos don't exist,

.....

Post by spudnik
every technique has problems.  like,

----

Post by spudnik
... etc. ad vomitorium).

With friendly greetings
Hero

[master1729]

Post by noemata
First, I have to say that I'm not a mathematician.
Maybe that's why I
don't understand why the four color theorem has been
so difficult to
prove.
The theorem states that no more than four colors are
necessary to
color
the regions of any map to separate them.
First you try to draw a counterexample. Then you
realize it's
impossible. And then you realize why: All the regions
have to touch
all
other regions - three goes fine, the fourth has to
surround at least
one
of them which in turn frees its color for reuse.
This problem seems to translate nicely into graph
theory where the
colors are dots and their contacts are lines between.
Given this, it's
possible to draw a graph with 1, 2, 3 and 4 dots with
lines connecting
all-to-all without any line crossing each other. If
you try to add a
5.
dot, its connecting lines will have to cross an
existing line; so,
it's
not possible to draw a graph with five dots without
any line crossing
http://noemata.net/ontheball/graph-4-color-theorem.png
This seems trivial, so why has the theorem been
difficult to prove?
Restating the theorem as: It is impossible to draw a
two-dimensional
map
where five or more colors are necessary, it then
seems intuitively
true
via graph theory. Now the problem might still exist,
in the word
"necessary" - who knows?
For me this is proof enough. On the other hand my
ideas are often
crank... But what's wrong?

i have a proof using infinite descent.

[master1729]

Post by noemata

Post by noemata
First, I have to say that I'm not a mathematician.
Maybe that's why I
don't understand why the four color theorem has

been

Post by noemata
so difficult to
prove.
The theorem states that no more than four colors

are

Post by noemata
necessary to
color
the regions of any map to separate them.
First you try to draw a counterexample. Then you
realize it's
impossible. And then you realize why: All the

regions

Post by noemata
have to touch
all
other regions - three goes fine, the fourth has to
surround at least
one
of them which in turn frees its color for reuse.
This problem seems to translate nicely into graph
theory where the
colors are dots and their contacts are lines

between.

Post by noemata
Given this, it's
possible to draw a graph with 1, 2, 3 and 4 dots

with

Post by noemata
lines connecting
all-to-all without any line crossing each other.

If

Post by noemata
you try to add a
5.
dot, its connecting lines will have to cross an
existing line; so,
it's
not possible to draw a graph with five dots

without

Post by noemata
any line crossing

http://noemata.net/ontheball/graph-4-color-theorem.png

Post by noemata
This seems trivial, so why has the theorem been
difficult to prove?
Restating the theorem as: It is impossible to draw

a

Post by noemata
two-dimensional
map
where five or more colors are necessary, it then
seems intuitively
true
via graph theory. Now the problem might still

exist,

Post by noemata
in the word
"necessary" - who knows?
For me this is proof enough. On the other hand my
ideas are often
crank... But what's wrong?

i have a proof using infinite descent.

in fact i even have the most efficient algoritm.

[spudnik]

an argument by infinite descent would take a long time,
if you actually have a way of encoding a planar graph
as some thing; yeah.

- Hide quoted text -

[riderofgiraffes]

Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.

Draw a pentagon, put a vertex in the middle (giving
six vertices in total) and join that middle vertex
to the five on the pentagon. You cannot find four
vertices that are all mutually joined, so by your
reasoning, it should not be necessary to require
four colours. Three should suffice.

And yet three do not suffice. The structure of the
graph forces you to use four, even though you do not
have four mutually joined vertices.

In a similary fashion, perhaps there is a complex
graph where the requirement for a fifth colour does
not depend on local properties, but on global ones.
A cycle can be two coloured if there are an even
number of vertices, and yet not if there are an odd
number of vertices.

[noemata]

Post by riderofgiraffes
Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.

I don't think it follows logically. You say:
If x, then y. Conclusion: if not x, then not y.
But that's not true, you can have y in another way.
If it rains, then it gets wet. Conclusion: if it doesn't rain, it
doesn't get wet. But it might still be wet, for other reasons.

My argument I think goes like: Since it's impossible to mutually join
5 dots then it's impossible that 5 regions all have contact with each
other. And because of that a map where 5 colors are necessary is
impossible.

As I understand it now the problem of the proof is that a map that
needs 5 colors /is not necessarily/ a map where 5 regions have contact
with each other. One imagines that such a map exists in some
complicated way, but cannot find it. So I guess my question remains -
why aren't we able to prove somehow that a map that needs 5 colors is
structurally identical to a map where 5 regions have contact with each
other?

Post by riderofgiraffes
Draw a pentagon, put a vertex in the middle (giving
six vertices in total) and join that middle vertex
to the five on the pentagon.  You cannot find four
vertices that are all mutually joined, so by your
reasoning, it should not be necessary to require
four colours.  Three should suffice.
And yet three do not suffice.  The structure of the
graph forces you to use four, even though you do not
have four mutually joined vertices.
In a similary fashion, perhaps there is a complex
graph where the requirement for a fifth colour does
not depend on local properties, but on global ones.
A cycle can be two coloured if there are an even
number of vertices, and yet not if there are an odd
number of vertices.

[riderofgiraffes]

Post by noemata

Post by riderofgiraffes
Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.

I don't think it follows logically.

Let me say again. Your argument appears to be this:

"It's impossible to have 5 mutually adjacent points,
therefore it's impossible to require 5 colours."

That's my understanding of your argument.

That argument is not valid.

If that argument were valid, this would also be valid.

"If a map requires 5 colours then it must have five
mutually adjacent points."

If that argument were valid, then so would this:

"If a map requires four colours then it must have
four mutually adjacent points."

But we know that last argument is invalid, because
there are maps that require four colours, and yet
which do not have four adjacent points.

Post by noemata
If x, then y. Conclusion: if not x, then not y.

No. that's not true, and it's not what I said.
It's also mostly irrelevent for this discussion.

Post by noemata
Since it's impossible to mutually join 5 dots then
it's impossible that 5 regions all have contact with
each other.

OK, that's true.

Post by noemata
And because of that a map where 5 colors are
necessary is impossible.

Why? Is it simply because you can't imagine a situation
where you have a map requiring 5 colours and yet which
doesn't have 5 adjacent regions?

Not good enough.

Post by noemata
As I understand it now the problem of the proof is
that a map that needs 5 colors /is not necessarily/
a map where 5 regions have contact with each other.

Correct.

Post by noemata
One imagines that such a map exists in some
complicated way, but cannot find it. So I guess
my question remains - why aren't we able to prove
somehow that a map that needs 5 colors is
structurally identical to a map where 5 regions
have contact with each other?

To the best of my knowledge that's an interesting and
useful conjecture, and it has been pursued. However,
no proof using that approach has been produced. Here
is what you seem to be saying:

Conjecture: Any planar graph that requires 5 colours
for a vertex colouring is (in some sense yet to be
determined or defined) "structurally equivalent" to
K_5 - the complete graph on 5 points.

It's a valid method of attack, and it would be
interesting to see how far you get with it.

[noemata]

Post by riderofgiraffes

Post by noemata

Post by riderofgiraffes
Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.

I don't think it follows logically.

"It's impossible to have 5 mutually adjacent points,
therefore it's impossible to require 5 colours."
That's my understanding of your argument.
That argument is not valid.
If that argument were valid, this would also be valid.
"If a map requires 5 colours then it must have five
mutually adjacent points."
"If a map requires four colours then it must have
four mutually adjacent points."
But we know that last argument is invalid, because
there are maps that require four colours, and yet
which do not have four adjacent points.

Post by noemata
If x, then y. Conclusion: if not x, then not y.

No.  that's not true, and it's not what I said.
It's also mostly irrelevent for this discussion.

Post by noemata
Since it's impossible to mutually join 5 dots then
it's impossible that 5 regions all have contact with
each other.

OK, that's true.

Post by noemata
And because of that a map where 5 colors are
necessary is impossible.

Why?  Is it simply because you can't imagine a situation
where you have a map requiring 5 colours and yet which
doesn't have 5 adjacent regions?
Not good enough.

Post by noemata
As I understand it now the problem of the proof is
that a map that needs 5 colors /is not necessarily/
a map where 5 regions have contact with each other.

Correct.

Post by noemata
One imagines that such a map exists in some
complicated way, but cannot find it. So I guess
my question remains - why aren't we able to prove
somehow that a map that needs 5 colors is
structurally identical to a map where 5 regions
have contact with each other?

To the best of my knowledge that's an interesting and
useful conjecture, and it has been pursued.  However,
no proof using that approach has been produced.  Here
Conjecture: Any planar graph that requires 5 colours
for a vertex colouring is (in some sense yet to be
determined or defined) "structurally equivalent" to
K_5 - the complete graph on 5 points.
It's a valid method of attack, and it would be
interesting to see how far you get with it.

Thanks for very useful comments, many of the comments here are, it's a
great help. If any comments I made were inappropriate, please put it

Post by riderofgiraffes
"If a map requires 5 colours then it must have five
mutually adjacent points."
"If a map requires four colours then it must have
four mutually adjacent points."

I don't think the problem can be reduced like this. A complete graph
of 5 points might be "qualitatively different" from one of 4 points in
some respect. For instance, can adding points somehow be like adding
dimensions - a 4D structure has different qualitites than a 5D
structure? Or to take a silly example: If 5 workers can produce 5
cars, it doesn't mean that 4 workers can produce 4 cars. Maybe the
production line requires 5 workers to produce at all. Again, sorry for
the silly example, but I think it's valid.

Now, probably it's better for me to study the answers and theorem more
rather than to think aloud - thanks again for useful help.

Bjørn

[riderofgiraffes]

Post by noemata
Thanks for very useful comments, many of the comments
here are, it's a great help. If any comments I made
were inappropriate, please put it on my slow-wittedness.

Nothing was inappropriate, and some of these issues are
obscure and difficult.

Post by noemata

Post by riderofgiraffes
"If a map requires 5 colours then it must have
five mutually adjacent points."
"If a map requires four colours then it must have
four mutually adjacent points."

I don't think the problem can be reduced like this.
A complete graph of 5 points might be "qualitatively
different" from one of 4 points in some respect.

If it is qualitatively different then you need to
include that in your statement. As it was, you seemed
to be saying that requiring five colours must in and
of itself imply that there are five mutually adjacent
points. Maybe it does, maybe it doesn't, but it's not
right to make that claim without then qualifying it.

As stated, your method of reasoning seems to apply
equally well to the four colour requires K_4 case,
and we know that to be false. That then implies that
the reasoning is faulty. If there is something
special that starts to make it work in the five
colour case then you need to make that clear.

And as I said, you might be right. It might be the
case that a planar graph requiring five colours does
then imply the existence of a planar K_5. If you
can prove that then you have a valid proof of the
4CT, the first one that doesn't require a computer.

Post by noemata
Now, probably it's better for me to study the
answers and theorem more rather than to think
aloud - thanks again for useful help.

Sometimes you need to mess around with things on
your own first, before reading other people's
proofs. Then you are in a better position to
understand the subtlties and difficulties.

Besides, sometimes you might find a proof that no
one else has found. Unlikely, but possible.

never stop experimenting.

Post by noemata
Bjørn

Rider.

[noemata]

Reading and trying to reformulate of my argument:
(1) A map that needs n colours contains a K_n as graph.
(2) All maps can be restated as planar graphs.
Then, a map that needs more than 4 colours is impossible because it
would contain a non-planar K5 as graph.

What about the counterexamples given, for example the pentagon graph
needing 3 colours while only having 2 mutually joined vertices? I
understand this as: while all maps can be restated as planar graphs,
not all planar graphs can be restated as maps. When I try to draw the
pentagon graph as map it reduces to a K3 as graph, which supports (1).
There isn't a direct way to draw a map from a graph - the example with
a pentagon with a vertex in the middle that requires 4 colours makes
this clearer. But there might be a procedure for this purpose that
reduces a planar graph to a K_n. For example, the node-list of the
pentagon shows that a couple of nodes are redundant and so leaving us
with a K3:
1: 2, 3
2: 1 (redundant, already in "2: 3, 1")
1: 2 (redundant, already in "1: 2, 3")
2: 3, 1
3: 1, 2

In this way, would a simplified proof of 4CT be possible? Since 4CT,
as I understand it, is proven for all planar graphs, though not all
planar graphs are maps, the proof is more complicated than necessary.
Maybe all planar graphs /are/ maps, though not restate-able in a
direct way. Maybe all graphs can be reduced to maps. My idea is that
all planar graphs are reducible to a map as a K_n graph and thus
requiring n colours.

Grateful for comments, my main concern is the relation between maps
and graphs.
-Bjørn

Post by riderofgiraffes

Post by noemata
Thanks for very useful comments, many of the comments
here are, it's a great help. If any comments I made
were inappropriate, please put it on my slow-wittedness.

Nothing was inappropriate, and some of these issues are
obscure and difficult.

Post by noemata

Post by riderofgiraffes
"If a map requires 5 colours then it must have
five mutually adjacent points."
"If a map requires four colours then it must have
four mutually adjacent points."

I don't think the problem can be reduced like this.
A complete graph of 5 points might be "qualitatively
different" from one of 4 points in some respect.

If it is qualitatively different then you need to
include that in your statement. As it was, you seemed
to be saying that requiring five colours must in and
of itself imply that there are five mutually adjacent
points.  Maybe it does, maybe it doesn't, but it's not
right to make that claim without then qualifying it.
As stated, your method of reasoning seems to apply
equally well to the four colour requires K_4 case,
and we know that to be false. That then implies that
the reasoning is faulty.  If there is something
special that starts to make it work in the five
colour case then you need to make that clear.
And as I said, you might be right.  It might be the
case that a planar graph requiring five colours does
then imply the existence of a planar K_5.  If you
can prove that then you have a valid proof of the
4CT, the first one that doesn't require a computer.

Post by noemata
Now, probably it's better for me to study the
answers and theorem more rather than to think
aloud - thanks again for useful help.

Sometimes you need to mess around with things on
your own first, before reading other people's
proofs.  Then you are in a better position to
understand the subtlties and difficulties.
Besides, sometimes you might find a proof that no
one else has found.  Unlikely, but possible.
never stop experimenting.

Post by noemata
Bjørn

Rider.

[Chip Eastham]

Post by noemata
(1) A map that needs n colours contains a K_n as graph.
(2) All maps can be restated as planar graphs.
Then, a map that needs more than 4 colours is impossible because it
would contain a non-planar K5 as graph.
What about the counterexamples given, for example the pentagon graph
needing 3 colours while only having 2 mutually joined vertices? I
understand this as: while all maps can be restated as planar graphs,
not all planar graphs can be restated as maps. When I try to draw the
pentagon graph as map it reduces to a K3 as graph, which supports (1).
There isn't a direct way to draw a map from a graph - the example with
a pentagon with a vertex in the middle that requires 4 colours makes
this clearer. But there might be a procedure for this purpose that
reduces a planar graph to a K_n. For example, the node-list of the
pentagon shows that a couple of nodes are redundant and so leaving us
1: 2, 3
2: 1 (redundant, already in "2: 3, 1")
1: 2 (redundant, already in "1: 2, 3")
2: 3, 1
3: 1, 2
In this way, would a simplified proof of 4CT be possible? Since 4CT,
as I understand it, is proven for all planar graphs, though not all
planar graphs are maps, the proof is more complicated than necessary.
Maybe all planar graphs /are/ maps, though not restate-able in a
direct way. Maybe all graphs can be reduced to maps. My idea is that
all planar graphs are reducible to a map as a K_n graph and thus
requiring n colours.
Grateful for comments, my main concern is the relation between maps
and graphs.
-Bjørn

Post by riderofgiraffes

Post by noemata
Thanks for very useful comments, many of the comments
here are, it's a great help. If any comments I made
were inappropriate, please put it on my slow-wittedness.

Nothing was inappropriate, and some of these issues are
obscure and difficult.

Post by noemata

Post by riderofgiraffes
"If a map requires 5 colours then it must have
five mutually adjacent points."
"If a map requires four colours then it must have
four mutually adjacent points."

I don't think the problem can be reduced like this.
A complete graph of 5 points might be "qualitatively
different" from one of 4 points in some respect.

If it is qualitatively different then you need to
include that in your statement. As it was, you seemed
to be saying that requiring five colours must in and
of itself imply that there are five mutually adjacent
points.  Maybe it does, maybe it doesn't, but it's not
right to make that claim without then qualifying it.
As stated, your method of reasoning seems to apply
equally well to the four colour requires K_4 case,
and we know that to be false. That then implies that
the reasoning is faulty.  If there is something
special that starts to make it work in the five
colour case then you need to make that clear.
And as I said, you might be right.  It might be the
case that a planar graph requiring five colours does
then imply the existence of a planar K_5.  If you
can prove that then you have a valid proof of the
4CT, the first one that doesn't require a computer.

Post by noemata
Now, probably it's better for me to study the
answers and theorem more rather than to think
aloud - thanks again for useful help.

Sometimes you need to mess around with things on
your own first, before reading other people's
proofs.  Then you are in a better position to
understand the subtlties and difficulties.
Besides, sometimes you might find a proof that no
one else has found.  Unlikely, but possible.
never stop experimenting.

Post by noemata
Bjørn

Rider.

I don't understand why you say that in drawing the
"pentagon graph as map it reduces to a K3 as graph."

To illustrate the ring of 5 regions in "map" form
as opposed to "graph" form, take a circle and from
the center draw five distinct radial line segments.

The five "slices of the pie" are the regions, and
each has two adjacent regions. No three regions
are mutually adjacent, so there is no K_3 (triangle)
in the corresponding (planar) graph. Yet the map
requires 3 colors.

regards, chip

[noemata]

Post by Chip Eastham

Post by noemata
(1) A map that needs n colours contains a K_n as graph.
(2) All maps can be restated as planar graphs.
Then, a map that needs more than 4 colours is impossible because it
would contain a non-planar K5 as graph.
What about the counterexamples given, for example the pentagon graph
needing 3 colours while only having 2 mutually joined vertices? I
understand this as: while all maps can be restated as planar graphs,
not all planar graphs can be restated as maps. When I try to draw the
pentagon graph as map it reduces to a K3 as graph, which supports (1).
There isn't a direct way to draw a map from a graph - the example with
a pentagon with a vertex in the middle that requires 4 colours makes
this clearer. But there might be a procedure for this purpose that
reduces a planar graph to a K_n. For example, the node-list of the
pentagon shows that a couple of nodes are redundant and so leaving us
1: 2, 3
2: 1 (redundant, already in "2: 3, 1")
1: 2 (redundant, already in "1: 2, 3")
2: 3, 1
3: 1, 2
In this way, would a simplified proof of 4CT be possible? Since 4CT,
as I understand it, is proven for all planar graphs, though not all
planar graphs are maps, the proof is more complicated than necessary.
Maybe all planar graphs /are/ maps, though not restate-able in a
direct way. Maybe all graphs can be reduced to maps. My idea is that
all planar graphs are reducible to a map as a K_n graph and thus
requiring n colours.
Grateful for comments, my main concern is the relation between maps
and graphs.
-Bjørn

Post by riderofgiraffes

Post by noemata
Thanks for very useful comments, many of the comments
here are, it's a great help. If any comments I made
were inappropriate, please put it on my slow-wittedness.

Nothing was inappropriate, and some of these issues are
obscure and difficult.

Post by noemata

Post by riderofgiraffes
"If a map requires 5 colours then it must have
five mutually adjacent points."
"If a map requires four colours then it must have
four mutually adjacent points."

I don't think the problem can be reduced like this.
A complete graph of 5 points might be "qualitatively
different" from one of 4 points in some respect.

If it is qualitatively different then you need to
include that in your statement. As it was, you seemed
to be saying that requiring five colours must in and
of itself imply that there are five mutually adjacent
points.  Maybe it does, maybe it doesn't, but it's not
right to make that claim without then qualifying it.
As stated, your method of reasoning seems to apply
equally well to the four colour requires K_4 case,
and we know that to be false. That then implies that
the reasoning is faulty.  If there is something
special that starts to make it work in the five
colour case then you need to make that clear.
And as I said, you might be right.  It might be the
case that a planar graph requiring five colours does
then imply the existence of a planar K_5.  If you
can prove that then you have a valid proof of the
4CT, the first one that doesn't require a computer.

Post by noemata
Now, probably it's better for me to study the
answers and theorem more rather than to think
aloud - thanks again for useful help.

Sometimes you need to mess around with things on
your own first, before reading other people's
proofs.  Then you are in a better position to
understand the subtlties and difficulties.
Besides, sometimes you might find a proof that no
one else has found.  Unlikely, but possible.
never stop experimenting.

Post by noemata
Bjørn

Rider.

I don't understand why you say that in drawing the
"pentagon graph as map it reduces to a K3 as graph."
To illustrate the ring of 5 regions in "map" form
as opposed to "graph" form, take a circle and from
the center draw five distinct radial line segments.
The five "slices of the pie" are the regions, and
each has two adjacent regions.  No three regions
are mutually adjacent, so there is no K_3 (triangle)
in the corresponding (planar) graph.  Yet the map
requires 3 colors.
regards, chip

Yes it's convincing. I didn't realize it before, though it does seem
trivial.
Also, if you or anyone has a quick answer: is it so that every planar
graph can be directly restated as a map?

Jake Wildstrom in the previous post made me realize I was more or less
trying to reformulate Hadwiger's conjecture. In mathematical terms
what i meant with the expression "pentagon graph as map reduces to a
K3 as graph" is that the pentagon graph is "edge-contracted to a 3-
cycle, that is, a K3 minor.", as it says on
http://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)#Special_cases

Sorry if I have wasted anyone's time,
thanks and regards,
Bjørn

[jbriggs444]

Post by noemata

Post by riderofgiraffes

Post by noemata

Post by riderofgiraffes
Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.

I don't think it follows logically.

"It's impossible to have 5 mutually adjacent points,
therefore it's impossible to require 5 colours."
That's my understanding of your argument.
That argument is not valid.
If that argument were valid, this would also be valid.
"If a map requires 5 colours then it must have five
mutually adjacent points."
"If a map requires four colours then it must have
four mutually adjacent points."
But we know that last argument is invalid, because
there are maps that require four colours, and yet
which do not have four adjacent points.

Post by noemata
If x, then y. Conclusion: if not x, then not y.

No.  that's not true, and it's not what I said.
It's also mostly irrelevent for this discussion.

Post by noemata
Since it's impossible to mutually join 5 dots then
it's impossible that 5 regions all have contact with
each other.

OK, that's true.

Post by noemata
And because of that a map where 5 colors are
necessary is impossible.

Why?  Is it simply because you can't imagine a situation
where you have a map requiring 5 colours and yet which
doesn't have 5 adjacent regions?
Not good enough.

Post by noemata
As I understand it now the problem of the proof is
that a map that needs 5 colors /is not necessarily/
a map where 5 regions have contact with each other.

Correct.

Post by noemata
One imagines that such a map exists in some
complicated way, but cannot find it. So I guess
my question remains - why aren't we able to prove
somehow that a map that needs 5 colors is
structurally identical to a map where 5 regions
have contact with each other?

To the best of my knowledge that's an interesting and
useful conjecture, and it has been pursued.  However,
no proof using that approach has been produced.  Here
Conjecture: Any planar graph that requires 5 colours
for a vertex colouring is (in some sense yet to be
determined or defined) "structurally equivalent" to
K_5 - the complete graph on 5 points.
It's a valid method of attack, and it would be
interesting to see how far you get with it.

Thanks for very useful comments, many of the comments here are, it's a
great help. If any comments I made were inappropriate, please put it

Post by riderofgiraffes
"If a map requires 5 colours then it must have five
mutually adjacent points."
"If a map requires four colours then it must have
four mutually adjacent points."

I don't think the problem can be reduced like this. A complete graph
of 5 points might be "qualitatively different" from one of 4 points in
some respect. For instance, can adding points somehow be like adding
dimensions - a 4D structure has different qualitites than a 5D
structure? Or to take a silly example: If 5 workers can produce 5
cars, it doesn't mean that 4 workers can produce 4 cars. Maybe the
production line requires 5 workers to produce at all. Again, sorry for
the silly example, but I think it's valid.

It's not a question of reducing the problem. It's a question of
reducing
your argument (which I have not read, so take this with a grain of
salt).

If your argument is not crucially sensitive to some qualitative
distinction
between four colors and five then it applies with equal force to
the four color case. If it is invalid for the four color case (as it
is,
since there are counter-examples) then it is invalid for the five
color
case -- even if there are no counter-examples in that case.

[christian.bau]

Post by noemata
Now, probably it's better for me to study the answers and theorem more
rather than to think aloud - thanks again for useful help.

It might be a good idea to google for "five colour theorem" or "five
color theorem" - that's the theorem that every graph can be coloured
using FIVE different colours. Obviously a much weaker theorem, but
still not easy to prove. You'll find the proof on the internet - not
more than page. The idea, and I hope you can follow the logic: Let's
say not every map can be coloured with five colours. Let's say there
are maps that need six colours to colour them, and no way to do it
with five colours. Now if there are such maps, then there must be one
with the smallest possible number of countries.(All maps up to a
certain number of countries can be coloured in five colours, and with
one more country you'll find maps that absolutely need six colours).

So there must be a map that needs six colours, but if you remove any
country, it can be coloured in five. Then there is a formula for the
number of edges in a planar graph, and that formula shows that in a
planar graph you can't have all countries having six or more
neighbours, there must be some with five or fewer. So you take this
graph that needs six colours. You remove a country with five or fewer
neighbours. You colour the rest in five colours, and then you put the
missing country back in. And then these guys prove that you could have
coloured the whole map in five colours instead of six.

The funny thing is that some time in the 19th century someone made a
proof for the Four Colour Theorem using exactly the same idea, just a
little bit more complicated - and it took eleven years until a tiny
fault in the proof was discovered!

So you should definitely have a look at the Five Colour Theorem.

[Jake Wildstrom]

Post by riderofgiraffes

Post by noemata
One imagines that such a map exists in some
complicated way, but cannot find it. So I guess
my question remains - why aren't we able to prove
somehow that a map that needs 5 colors is
structurally identical to a map where 5 regions
have contact with each other?

To the best of my knowledge that's an interesting and
useful conjecture, and it has been pursued. However,
no proof using that approach has been produced. Here
Conjecture: Any planar graph that requires 5 colours
for a vertex colouring is (in some sense yet to be
determined or defined) "structurally equivalent" to
K_5 - the complete graph on 5 points.

A point worth investigation here -- if by "structurally equivalent",
you mean "has as a minor", which is definitely a form of substructure,
then what you are saying is in fact an extensively researched problem,
namely Hadwiger's conjecture. Hadwiger's conjecture states that if a
graph requires k or more colors, then the graph has a K_k as a minor
(a minor being the result of "gathering together" any number of
adjacent points and then taking a subgraph).

The good news: Hadwiger's conjecture has been proven in the case
k=5. The bad news: the proof is dependent on the Four-Color theorem
being true in the first place.

-Jake

[David Rusin]

Post by riderofgiraffes
Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.

Well, maybe you should say "In the spirit we might expect..." instead
of "That means..." .

It might be helpful to the OP to demonstrate a graph that really requires
5 colors but contains no K_5 . Building on the examples of other posts
we might begin with a ring of 5 points (the vertices of a pentagon) and
add two more vertices, each connected to all 5 of the original points
as well as to each other. That way the pentagon requires 3 colors and
each of the additional points requires an additional color. On the other
hand any set of 5 mutually adjacent points would have to include at
least 3 points of the pentagon, and no such set of 3 mutually adjacent
points exists.

This particular graph is not a counterexample to the 4CT because it is
not planar, but the fact that it is not planar is not especially obvious,
and moreover there is no obvious way to use the planarity of the graph
to rule out a similar but more complex example that IS planar.

dave

[riderofgiraffes]

To emphasise to the original poster, this reply from
David Rusin is excellent and deserves close study.

Post by riderofgiraffes
Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.
Well, maybe you should say "In the spirit we might
expect..." instead of "That means..." .
It might be helpful to the OP to demonstrate a graph
that really requires 5 colors but contains no K_5.
Building on the examples of other posts we might begin
with a ring of 5 points (the vertices of a pentagon)
and add two more vertices, each connected to all 5
of the original points as well as to each other. That
way the pentagon requires 3 colors and each of the
additional points requires an additional color. On
the other hand any set of 5 mutually adjacent points
would have to include at least 3 points of the pentagon,
and no such set of 3 mutually adjacent points exists.
This particular graph is not a counterexample to the
4CT because it is not planar, but the fact that it is
not planar is not especially obvious, and moreover
there is no obvious way to use the planarity of the
graph to rule out a similar but more complex example
that IS planar.
dave

[noemata]

Post by riderofgiraffes
To emphasise to the original poster, this reply from
David Rusin is excellent and deserves close study.

Post by riderofgiraffes
Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.
Well, maybe you should say "In the spirit we might
expect..." instead of "That means..." .
It might be helpful to the OP to demonstrate a graph
that really requires 5 colors but contains no K_5.
Building on the examples of other posts we might begin
with a ring of 5 points (the vertices of a pentagon)
and add two more vertices, each connected to all 5
of the original points as well as to each other. That
way the pentagon requires 3 colors and each of the
additional points requires an additional color. On
the other hand any set of 5 mutually adjacent points
would have to include at least 3 points of the pentagon,
and no such set of 3 mutually adjacent points exists.
This particular graph is not a counterexample to the
4CT because it is not planar, but the fact that it is
not planar is not especially obvious, and moreover
there is no obvious way to use the planarity of the
graph to rule out a similar but more complex example
that IS planar.
dave

I understand the example finally if the last line says 5 instead of 3,
because sets of 3 mutually adjacent points exist.

From the comments I've had to modify the original idea to be "a graph
that needs n colours can be /reduced/ to contain K_n", which turns out
to be Hadwiger's conjecture given the proper "reduction" (contracting
the edges of its k disjoint connected subgraphs to a K_n as minor).

regards, Bjørn

[Gerry Myerson]

In article

Post by noemata

Post by riderofgiraffes
To emphasise to the original poster, this reply from
David Rusin is excellent and deserves close study.

Post by riderofgiraffes
Your argument is that because you cannot have five
mutually joined points, five colours cannot be
necessary. That means that if I have a graph without
four mutually joined points, four colours won't be
necessary.
Well, maybe you should say "In the spirit we might
expect..." instead of "That means..." .
It might be helpful to the OP to demonstrate a graph
that really requires 5 colors but contains no K 5.
Building on the examples of other posts we might begin
with a ring of 5 points (the vertices of a pentagon)
and add two more vertices, each connected to all 5
of the original points as well as to each other. That
way the pentagon requires 3 colors and each of the
additional points requires an additional color. On
the other hand any set of 5 mutually adjacent points
would have to include at least 3 points of the pentagon,
and no such set of 3 mutually adjacent points exists.
This particular graph is not a counterexample to the
4CT because it is not planar, but the fact that it is
not planar is not especially obvious, and moreover
there is no obvious way to use the planarity of the
graph to rule out a similar but more complex example
that IS planar.
dave

I understand the example finally if the last line says 5 instead of 3,
because sets of 3 mutually adjacent points exist.

Yes, but no *such* sets exist, where "such" means
3 points of the pentagon. No 3 points of the pentagon
that you begin with are mutually adjacent, therefore
no set of 5 mutually adjacent points exists.

[spudnik]

yes; a "complete graph on five points" is
a what-you-call-it, having diagonals that
(by definition?) cross each-other, which
is not a "simple graph" that is dual
to the map, whose edges & vertices also
constitute a simple graph, simply connected,
with (connected) oceans counting as "no color" (or
a color .-)

Post by Gerry Myerson
no set of 5 mutually adjacent points exists.

thus & so:
what is a reasonable investment in rebinding, iff
"the book is of value to me, myself & y'know," if
y'know; or what is the best DIY format?

I'm sure there are at least two of them
in the old catalog-can-you-fax-it-over-to-here?

what's the URL?

Post by Gerry Myerson
I asked them years ago when they started gluing their signatures. No
answer ever came. (Amusingly enough, I still have a signature-sewn
catalogue from them.)

thus:
prove and/or define the most canonical "law
of cosines" in trgionometry, you can;
you can define "canonical," two.

well, I just read the definition
of the law, or the supposed outcome of formula
-- which is completely standard, as far as I can tell --
in a large dictionary (of English).

thus:
I haven't proven that the Bible Code was a hoax;
only a hueristical argument about any ring
of "letters of all of letters" ... not the Object or
Bunny Rings, neccesarily. however,
the biblical topic is "skip codes."

Post by Gerry Myerson
Where..Easter bunny..him?

--Light: A History!
http://wlym .com

[Gerry Myerson]

In article

Post by noemata
First, I have to say that I'm not a mathematician. Maybe that's why I
don't understand why the four color theorem has been so difficult to
prove.
The theorem states that no more than four colors are necessary to
color
the regions of any map to separate them.
First you try to draw a counterexample. Then you realize it's
impossible. And then you realize why: All the regions have to touch
all
other regions

There's your mistake. It is indeed easy to prove that you can't
draw 5 regions so each touches all the others, but that doesn't
even begin to prove the 4CT. You have to deal with the possibility
that there's a map with lots of regions that needs 5 colors even
though no 5 of its regions are mutually adjacent.

Think about coloring the vertices of a pentagon. There is no set
of 3 vertices, all adjacent to each other, but you still need 3 colors.

[spudnik]

to put it differently, Bucky thought that "behold,
the tetrahedron" was a proof of 4CT, but
it just shows the *neccesity* of (at least) four colors,
not the sufficiency thereof. (and, of course,
since the tetrahedron is self-dual,
you can color the vertices, instead. which is to say,
almost all treatments of 4CT use graphs, because
it is exactly equivalent.)

Post by Gerry Myerson
Think about coloring the vertices of a pentagon. There is no set
of 3 vertices, all adjacent to each other, but you still need 3 colors.

thus:
so, a lightmill is that thing with black & white vanes
on a spindle in a relative vacuum?
you can't rely on "rocks o'light" to impart momentum
to these vanes, only to be absorbed electromagnetically
by atoms in them; then, perhaps,
the "warm side" will have some aerodynamic/thermal effect
on the air in the bulb, compared to the cool one.
thus:
even if neutrinos don't exist,
Michelson and Morely didn't get no results!

Post by Gerry Myerson
Could neutrino availability affect decay rates?

thus:
every technique has problems. like,
you can't grow hemp-for haemorrhoids under a photovoltaic,
without a good lightbulb.
the real problem is that, if Santa Monica is any indication,
the solar-subsidy bandwagon is part of the cargo-cult
from Southwest Asia (as is the compact flourescent lightbub,
the LED lightbulb etc. ad vomitorium).

Post by Gerry Myerson
Government subsidies, and fat returns on PVs?

--Light: A History!
http://wlym.com

[noemata]

Post by Gerry Myerson
There's your mistake. It is indeed easy to prove that you can't
draw 5 regions so each touches all the others, but that doesn't
even begin to prove the 4CT. You have to deal with the possibility
that there's a map with lots of regions that needs 5 colors even
though no 5 of its regions are mutually adjacent.

Aha, now I see the problem. But it seems to be a problem of "proving"
something that seems intuitively true in graph theory. That a proof
has to deal with the possibility of a map that needs 5 colors seems to
me to be something like: prove that there are no naturally green swans
by checking all of them. And why should that constitute a proof since
there's no guarantee for not finding a green swan in the future?
Similarly, that another type of map, another formalism, should be
discovered later? This type of proof also seems arbitrary, like: prove
that no angels exist by dealing with the possibility that they exist.
A proof would for instance go through all types of angels (archangel,
seraphim, cherubim, etc) and on finding none of each conclude that no
angel exists. Or go through types of human senses and conclude that if
no angels are to be seen, heard, touched, etc. there's no need to
believe they exist. In short, it doesn't seem satisfactory to me that
a proof of 4CT has to deal with finding a possible map needing 5
colors. Because if this map doesn't exist, then 4CT cannot be proven
(by not finding it) - 4CT can only be proven wrong by finding such a
map. I guess it's a problem of falsifiability. It would be better with
an analytical proof, and I'm still not sure why a proof via graph
theory (as mentioned in the post) won't work, for instance by
establishing a structural identity between 4CT and the graph.
Thanks for your answer - Bjørn

[riderofgiraffes]

The 4CT claims that no planar map requires 5 colours. You
seem to think that the only way to prove that is to check
every planar map and see that it only requires 4 (at most).

An equivalent would be this. I claim that no number of
the form 4*k+3 can be written as the sum of two squares.
By your reasoning the only way to know this for certain
would be to check every number of the form 4*k+3 and see
that it cannot indeed be written as the sum of two
squares.

What mathematics is about, though, is proof, reasoning
by agreed techniques from agreed facts to show that other
statements follow logically, and hence must be true.

This has been done with the 4*k+3 statement, and it's been
done with the 4CT. It has been shown *by reasoning* that
no planar map requires 5 colours.

The reasoning is long, moderately difficult, and complex,
but it's now accepted as correct.

It is, by the way, comparatively easy to show that no
planar map requires 5 colours, and it's fairly trivial
to show that no planar map requires 6 colours. If you
are interested in this question, why don't you find
explanations of those and study them as a warm-up.

[Chip Eastham]

Post by noemata

Post by Gerry Myerson
There's your mistake. It is indeed easy to prove that you can't
draw 5 regions so each touches all the others, but that doesn't
even begin to prove the 4CT. You have to deal with the possibility
that there's a map with lots of regions that needs 5 colors even
though no 5 of its regions are mutually adjacent.

Aha, now I see the problem. But it seems to be a problem of "proving"
something that seems intuitively true in graph theory. That a proof
has to deal with the possibility of a map that needs 5 colors seems to
me to be something like: prove that there are no naturally green swans
by checking all of them. And why should that constitute a proof since
there's no guarantee for not finding a green swan in the future?
Similarly, that another type of map, another formalism, should be
discovered later? This type of proof also seems arbitrary, like: prove
that no angels exist by dealing with the possibility that they exist.
A proof would for instance go through all types of angels (archangel,
seraphim, cherubim, etc) and on finding none of each conclude that no
angel exists. Or go through types of human senses and conclude that if
no angels are to be seen, heard, touched, etc. there's no need to
believe they exist. In short, it doesn't seem satisfactory to me that
a proof of 4CT has to deal with finding a possible map needing 5
colors. Because if this map doesn't exist, then 4CT cannot be proven
(by not finding it) - 4CT can only be proven wrong by finding such a
map. I guess it's a problem of falsifiability. It would be better with
an analytical proof, and I'm still not sure why a proof via graph
theory (as mentioned in the post) won't work, for instance by
establishing a structural identity between 4CT and the graph.
Thanks for your answer - Bjørn

I think you missed riderofgiraffe's and Gerry's point, that
four color theorem requires eliminating the possibility of
maps that require five colors, not just the possibility of
five mutually adjacent regions. They gave you an example
to think about, a map in which no three regions are all
adjacent to one another (in fact each region has only two
neighbors that themselves do not touch), yet three colors
are required for coloring.

1
/ \
/ \
2 3
\ /
4-5

A "ring" of any odd number of regions (more than 3) will
illustrate this phenomenon.

A proof of 4CT has to "deal" with the possibility of a map
requiring five colors just in the sense that it must in
some way exclude this possibility (not, as you seem to say,
by "finding" one). The known proofs do this in a rather
concrete but tedious way (using computer checking) to show
all planar maps have a four coloring (by reducing the
number of cases to be checked to a large but finite number
of possibilities, to which an algorithm may be applied).
Although there are infinitely many different planar maps,
the finite number of cases to check is established by
analyzing "rings" of regions that divide the map into
a section inside the ring and one outside the ring.

You might be interested in these expositions:

[Last doubts removed about the proof of the Four Color Theorem]
(by Keith Devlin)
http://www.maa.org/devlin/devlin_01_05.html

[A computer-checked proof of the Four Colour Theorem]
(by George Gonthier)
http://research.microsoft.com/en-us/um/people/gonthier/4colproof.pdf

The Wikipedia and Wolfram Mathworld articles are also worth
a look.

regards, chip

[ICA]

Post by Chip Eastham

Post by noemata

Post by Gerry Myerson
There's your mistake. It is indeed easy to prove that you can't
draw 5 regions so each touches all the others, but that doesn't
even begin to prove the 4CT. You have to deal with the possibility
that there's a map with lots of regions that needs 5 colors even
though no 5 of its regions are mutually adjacent.

Aha, now I see the problem. But it seems to be a problem of "proving"
something that seems intuitively true in graph theory. That a proof
has to deal with the possibility of a map that needs 5 colors seems to
me to be something like: prove that there are no naturally green swans
by checking all of them. And why should that constitute a proof since
there's no guarantee for not finding a green swan in the future?
Similarly, that another type of map, another formalism, should be
discovered later? This type of proof also seems arbitrary, like: prove
that no angels exist by dealing with the possibility that they exist.
A proof would for instance go through all types of angels (archangel,
seraphim, cherubim, etc) and on finding none of each conclude that no
angel exists. Or go through types of human senses and conclude that if
no angels are to be seen, heard, touched, etc. there's no need to
believe they exist. In short, it doesn't seem satisfactory to me that
a proof of 4CT has to deal with finding a possible map needing 5
colors. Because if this map doesn't exist, then 4CT cannot be proven
(by not finding it) - 4CT can only be proven wrong by finding such a
map. I guess it's a problem of falsifiability. It would be better with
an analytical proof, and I'm still not sure why a proof via graph
theory (as mentioned in the post) won't work, for instance by
establishing a structural identity between 4CT and the graph.
Thanks for your answer - Bjørn

I think you missed riderofgiraffe's and Gerry's point, that
four color theorem requires eliminating the possibility of
maps that require five colors, not just the possibility of
five mutually adjacent regions.  They gave you an example
to think about, a map in which no three regions are all
adjacent to one another (in fact each region has only two
neighbors that themselves do not touch), yet three colors
are required for coloring.
         1
        / \
       /   \
      2     3
       \   /
        4-5
A "ring" of any odd number of regions (more than 3) will
illustrate this phenomenon.
A proof of 4CT has to "deal" with the possibility of a map
requiring five colors just in the sense that it must in
some way exclude this possibility (not, as you seem to say,
by "finding" one).  The known proofs do this in a rather
concrete but tedious way (using computer checking) to show
all planar maps have a four coloring (by reducing the
number of cases to be checked to a large but finite number
of possibilities, to which an algorithm may be applied).
Although there are infinitely many different planar maps,
the finite number of cases to check is established by
analyzing "rings" of regions that divide the map into
a section inside the ring and one outside the ring.
[Last doubts removed about the proof of the Four Color Theorem]
(by Keith Devlin)http://www.maa.org/devlin/devlin_01_05.html
[A computer-checked proof of the Four Colour Theorem]
(by George Gonthier)http://research.microsoft.com/en-us/um/people/gonthier/4colproof.pdf
The Wikipedia and Wolfram Mathworld articles are also worth
a look.
regards, chip

Odd rings of size greater than three is the main source of the
difficulty in the proof of the 4CT. In the revised version of my paper
"A Victorian Age Proof of the Four Color Theorem" ( http://arxiv.org/abs/0903.4108
) I have given an algorithm of breaking (or blocking) the big white
odd rings (if there is any) in the maximal di-chromatic map M(B,G)
where B denotes color brown for the high-land region and G denotes
color green for the low-land region.

Cahit

[rich39]

I never thought it should be as difficult as presented.
Here's a paper with a different approach.
insight.awardspace.info
What's your opinion?

[spudnik]

my opinion is that you got a trophy in a Spamshop --
for nothing but your "insightful information ... and
you can see why they chose that moniker;
every one likes Spam (tm), possibly forgoing the baked beans.

seriously, can you give us a precis or aone-liner or a title?

Post by rich39
What's your opinion?

thus & so:
nice cartoon; is there only one beamsplitter in Sagnac?

Post by rich39
be found here: http://tinyurl.com/3ac42y8

--Pi, the surfer's canonical value, is not constructible
with a pair of compasses .. but, could be with a pair and
a half of compasses; yes?

[spudnik]

hey; maybe tehy'd let you look at your trophy
with those 3d glasses!

thusNso:
dood, my valu of pi is lots simpler to calculate
than yours -- seven cans of beer & a string!

thusNso:
nice cartoon; is there only one beamsplitter in Sagnac?

--Pi, the surfer's canonical value, is not constructible
with a pair of compasses .. but, could be with a pair and
a half of compasses; dyscuss.

[noemata]

Post by rich39
I never thought it should be as difficult as presented.
Here's a paper with a different approach.
insight.awardspace.info
What's your opinion?

Very interesting for me since it formalizes my (simple) thoughts. I'm
able to follow most of the argument including recoloring and the
reduction of a graph to a basic object, but I'm not competent to tell
if the conclusion holds - that a 5c object is impossible because the
notion of causality is false.

"When the map is divided into boundaries, the coloring process
operates in each boundary independently of the others. The notion of
causality spreading through the links, and
therefore a larger map providing a possible configuration for the 5c
object, has been shown to be a false assumption. If all the links of a
map were necessary, none could be removed, and
reduction would not be possible. If the k colored basic 2D object
can't be formed with the first k nodes then it doesn't exist."

Thanks for posting
regards