So you only need four color's to color a map? What if all the localaties met at a single point? See the attached diagram. Lets a ssume the lines are perfect and borders intersect at a single point. Would that mean that more than 4 colors are needed?

Attached Images

four_color.gif (2.5 KB, 40 views)

__________________
MacTalk - The Australian Apple Community - iPod, iPhone and Mac.

Wikipedia: Four color theorem

The four color theorem states that any plane separated into regions, such as a political map of the counties of a state, can be colored using no more than four colors in such a way that no two adjacent regions receive the same color. Two regions are called adjacent if they share a border segment, not just a point.

__________________
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0....

There is a book, called Four Colours Suffice that gives the history of the problem. It is a layman's book, but the math level varies. Sometimes it is too simplistic. Other times it goes too fast, but in all, I have a better understanding of the proof than I did before I read it.

__________________
Rock is dead. Long live Paper and Scissors.

But have they proved it for all colours?

__________________
There are 10 types of people in the world. Those who understand ternary, those who don't, and those waiting for a bus.
If logic doesn't work, then surely it does.

I'm not sure I understand what you mean. It is trivial to prove that 3 or fewer colors is not sufficient. All you need is to show that there is a map where 3 colors aren't enough. Here is a simple counterexample: Start with a thick circle with a hole in the center. Section the circle into 3 parts, each of which must be a different color. The hole in the center must also be different from the first 3 colors used on the circle, which proves that 3 colors are too few. For 5 colors, take a 4 color map and arbitrarily change one of the areas to a color that isn't anywhere else on the map. For 6 colors, take the above mentioned 5 color map and change one area to a color that isn't yet used. Do this for as many colors as you have in your crayon box.

Attached Images

d.JPG (5.0 KB, 13 views)

__________________
Rock is dead. Long live Paper and Scissors.

I know what he means. **bap** now, say you're sorry

It has long been known that a map on a torus requires seven colors, and seven always suffices. To see that seven is necessary, take a torus, and divide it into bands of seven different regions encircling the torus through its hole. Now, cut a line around the top of the "donut" and slide the outside parts along the line 2 1/2 regions. All seven regions will share a boundary with all six other regions.

What I acutally meant was although it is true for the traditional colours used on a political map, has it also been proven for, say, 4 slightly different shades of pink.
Sorry.

__________________
There are 10 types of people in the world. Those who understand ternary, those who don't, and those waiting for a bus.
If logic doesn't work, then surely it does.

It doesn't matter which colors you use, as long as they are all different. So, yes, it would work for 4 different shades of pink because they are all different. It would also work for four shades of blue, green, maybe two of red and two of grey, etc.

Basically, when you have four countries that all touch each other, one of those contries has to be completely surrounded. Notice in jfribrg's diagram, the brown country is completely surrounded. Go ahead and try it yourself on a piece of paper.

There is, however, an unstated premise: All the countries have to be in one piece. For example, the United States is not in one piece because of Alaska. There are two large "pieces" of the U.S. (and various islands)... If you tried this on the actual map of the Earth, you might not find the 4 color theorem is true (then again, it might be. I've never tried it).

__________________
"Critical thinking and skepticism form the cornerstone of intelligence."
-me

Ok, thanks for the clarification

I think you would find that the 4 color theorem is true irrespective of the potential problem you raise, it just isn't the same thing you're describing.

__________________
There are 10 types of people in the world. Those who understand ternary, those who don't, and those waiting for a bus.
If logic doesn't work, then surely it does.

LOL. Yep. Just take any map of any set of N countries and put an "embassy" for each one, in each one. Then, you need N colors.

Exactly.

__________________
"Critical thinking and skepticism form the cornerstone of intelligence."
-me

Basically that is the key, but proving it is the problem.


Actually, this is stated explicitly in the formal definition of the problem.

Hawaii also, but the problem is limited to contiguous areas on a flat (two dimensional) surface that share a border. IIRC, for these purposes, Michigan is a problem too.

__________________
Rock is dead. Long live Paper and Scissors.

__________________
There are 10 types of people in the world. Those who understand ternary, those who don't, and those waiting for a bus.
If logic doesn't work, then surely it does.

Are there any practical applications for the four colour theorem or is it just one of those "neat things" to know like Fermat's Last Theorem and Relativity (Ha! Kidding!)

Pete

__________________
PJE

There's so much I don't know about astrophysics. I wish I had read that book by that wheelchair guy.

Maybe it's why there are CMYK printers - but that would suggest that there is a three colour theorem waiting to be proved.

__________________
There are 10 types of people in the world. Those who understand ternary, those who don't, and those waiting for a bus.
If logic doesn't work, then surely it does.

It is obviously useful for (game)mapmakers.

__________________
Join the Illuminati

I spent an entire summer as a kid trying to draw maps that would disprove the theorem. It wasn't a complete waste of time, because it did get me started down the path of scientific inquiry.

I was so naive when I first saw the problem that I figured that as it was obvious, I would be able to come up with a simple proof and dazzle the world

__________________
There are 10 types of people in the world. Those who understand ternary, those who don't, and those waiting for a bus.
If logic doesn't work, then surely it does.

My Uncle thought he had a proof of Fermat's Last theorem, less than a page. Even I found his mistake quickly.

He also had a "proof" that an angle can be trisected. I couldn't follow what he was doing, as it was purely geometrical, which I'm not familiar with

Well, gotta go!

Pete

__________________
PJE

There's so much I don't know about astrophysics. I wish I had read that book by that wheelchair guy.

I guess the problem would be not that Michigan comes in two pieces (they're easy enough to connect, at least on the map), but that neither Michigan and Illinois nor Indiana and Wisconsin share a border...