1. Established Member
Join Date
Jul 2005
Posts
1,704

## Four Color Theorem

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?

2. 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.

3. Established Member
Join Date
Mar 2002
Posts
2,379
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.

4. But have they proved it for all colours?

5. Established Member
Join Date
Mar 2002
Posts
2,379
Originally Posted by worzel
But have they proved it for all colours?
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.

6. 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.

7. 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.
Originally Posted by hhEb09'1
I know what he means. **bap** now, say you're sorry
Sorry.

8. 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).

9. Originally Posted by zrice03
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.
Ok, thanks for the clarification

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).
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.

10. 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.

11. Originally Posted by hhEb09'1
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.

12. Established Member
Join Date
Mar 2002
Posts
2,379
Originally Posted by zrice03
Basically, when you have four countries that all touch each other, one of those contries has to be completely surrounded.
Basically that is the key, but proving it is the problem.

Originally Posted by zrice03
There is, however, an unstated premise: All the countries have to be in one piece.
Actually, this is stated explicitly in the formal definition of the problem.

Originally Posted by zrice03
For example, the United States is not in one piece because of Alaska.
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.

13. Originally Posted by jfribrg
Originally Posted by zrice03
There is, however, an unstated premise: All the countries have to be in one piece.
Actually, this is stated explicitly in the formal definition of the problem.
Originally Posted by zrice03
Exactly.

14. Established Member
Join Date
Jan 2005
Posts
1,939
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

15. Originally Posted by peter eldergill
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
Maybe it's why there are CMYK printers - but that would suggest that there is a three colour theorem waiting to be proved.

16. ## 4 Colours

It is obviously useful for (game)mapmakers.

17. Member
Join Date
Nov 2003
Posts
46
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.

18. 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

19. Established Member
Join Date
Jan 2005
Posts
1,939
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

20. Originally Posted by jfribrg
IIRC, for these purposes, Michigan is a problem too.
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...

21. Originally Posted by peter eldergill
My Uncle thought he had a proof of Fermat's Last theorem, less than a page.
Maybe it was the same proof Fermat had

22. And we try to keep as much water as possible between us and Canada. (Here being Michigan) If the water is blue, does that count as a color?

I'm with Worzel here.

And what if the colors run?

Who among us before they were old enough to know how smart they weren't didn't figure, "Oh, I can beat that, lemme at it..."?

23. Originally Posted by Enzp
And we try to keep as much water as possible between us and Canada. (Here being Michigan)
Was just there a couple of weeks ago, didn't look like a particularly long bridge

24. Originally Posted by peter eldergill
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
Here's a way to trisect an angle.

25. Established Member
Join Date
Mar 2002
Posts
2,379
Originally Posted by hhEb09'1
Here's a way to trisect an angle.
From page 101 of the book "Elements of Abstract Algebra", which provides an interesting use of field theory to provide straightedge-and-compass proofs, this trisection is addressed.

First let us show how angles may be trisected easily if we allow and incorrect usage of the straightedge. (Apparently this practical construction was known to ancient geometers.)

As with other math problems, the "rules" are clearly defined. From the same book, here are the rules:
(1)the points (0,0) and (1,0) are constructible. Any two points of the plane may be chosen for (0,0) and (1,0) and the distance between them taken as the unit length.
(2) A circle with a constructible point as center and a constructible length as radius is constructible. A constructible length is the distance between two constructible points.
(3) The intersection of two constructible lines is a constructible point.
(4) The points (or point) of intersection of a constructible line and a constructible circle are constructible
(5) The points (or point) of intersection of two constructible circles are constructible
Step 3 in the link from the previous post is the illegal operation. The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.

The book then provides a single counterexample. First, the constructible points and operations are restated in terms of complex numbers, and a proof is given that these operations and points form a field. It then shows using field theory that it is impossible to trisect a 60 degree angle.

26. Originally Posted by jfribrg
Step 3 in the link from the previous post is the illegal operation. The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.
You could use the compass to measure the chord and then mark that off from E or F.

27. Originally Posted by jfribrg
Step 3 in the link from the previous post is the illegal operation.
Step 2 is also "illegal".

However, I use the straightedge legally, throughout.
The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.
No, it's not. As worzel points out, you can use that angle to easily construct a copy anywhere else, including between the original angle.

28. Montebianco - which bridge? Try walking that Mackinac bridge, she is longer than she looks. Every so often a car or truck blows over on it. We have our ways...

29. Two questions.

The first to jfribrg or anyone else who knows the answer. What purpose are those 5 rules of geometric construction supposed to serve given that they appear not to define what can actually be done, geometrically, with a straight edge and compass?

The second to hhEb09'1. Did you come up with that trisection yourself?

30. Originally Posted by worzel
The second to hhEb09'1. Did you come up with that trisection yourself?
The neusis or verging "cheat" trisections have been known for over two thousand years. That particular one is my modification of Archimedes's--which, according to The Book of Numbers by Conway and Guy, uses a marked ruler--which is an incorrect use of a ruler, as jfribrg's link says. Apparently, a lot of people know about the incorrect use of rulers, so I changed it to an incorrect use of a compass instead.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•