PDA

View Full Version : Only 4 are used!

jinx
05-14-2004, 01:28 PM
You can color any map using only four or less colors! I can't remember the name of the guy who proved this but its true. Can anyone prove me wrong?

I mean to say that the four colors allow no color to touch the same color on and edge (but the areas may share a vertex point).

Salem
05-14-2004, 01:42 PM
Ah, the old favourites....

axon
05-14-2004, 01:51 PM
>>Can anyone prove me wrong?

LOL...pft, why would we prove you wrong, if you didn't come up with that.

BTW, in my data structures and discrete math class, our prof said he will give out an A for the course if anyone can prove the theroem wrong...

Zach L.
05-14-2004, 02:47 PM
>> Can anyone prove me wrong?
Given a satisfactory set of axioms, quite easily.

RoD
05-14-2004, 03:13 PM
>>Can anyone prove me wrong?

Yes. Your are wrong because i am right. I cannot be wrong because i am right. There fore if im always right and you are not me, you are wrong and therefore i have proved you to be wrong.

DavidP
05-14-2004, 03:28 PM
try coloring this map with only 4 colors....

(yes the land formation is completely unrealistic, but still!)

jlou
05-14-2004, 03:39 PM
try coloring this map with only 4 colors....

(yes the land formation is completely unrealistic, but still!)Make the yellow and the green areas both be green, then make the uncolored area be yellow.

jlou
05-14-2004, 03:42 PM
Or if you wanted to fill in every area:

Glirk Dient
05-14-2004, 03:43 PM
What about a square divided into 4 equal parts(4 smaller squares) and completely surrounded by the same land.

Zach L.
05-14-2004, 04:58 PM
As I said, you just gotta play around with the axioms a bit. Here is a representation of one which (I am fairly sure, correct me if I am wrong) cannot be colored with only four colors. Its been umm... compressed sorta because I have no artistic skill, and a planar 2D space probably would not work for this kind of graph anyway, but the dots are colorable regions, and the lines between them signify that they share an edge.

DavidP
05-14-2004, 05:19 PM
echo Glirk Dient and Zach L.

JaWiB
05-14-2004, 06:59 PM
I'm assuming the theorem does not allow regions to lie entirely around other ones...If that's not the case then Glirk Dient is probably right. I've tried to represent Zach's here on top and Glirk's on bottom. Zach's doesn't seem to work because one of the colors (in this case, the green) would have to cross over another one. (The green could be light blue)

Edit: I accidentally didn't make the yellow area connect to the green on the top one, but it wouldn't make a difference

jlou
05-14-2004, 08:12 PM
Glirk Dient's won't work, because two areas are allowed to have the same color if they only touch at a point (the areas may share a vertex point).

In the top one for JaWiB, the light blue can be changed to dark green.

In the bottom one, I assume the light blue and the dark blue overlap by more than just a vertex. If so, the red one can be turned yellow (or the yellow can be turned red). If not, then it is like Glirk Dient's comment, and you only need three colors.

I don't see areas in Zach L.'s picture. How does it apply?

DavidP
05-14-2004, 08:49 PM
Zach's is more theoretical. His wont actually work on a single 2d plane, but would require a 3 dimensional representation because he has overlapping lines.

Zach L.
05-14-2004, 09:56 PM
Zach's is more theoretical. His wont actually work on a single 2d plane, but would require a 3 dimensional representation because he has overlapping lines.
Precisely! :D

jlou, as for the picture, I just decomposed it into the more graph theoretical representation. The maps can be represented as points (the colored areas), with lines connecting them (indicating that the two regions share an edge). The primary motivation for that particular representation is that I have no artistic skill.

jlou
05-14-2004, 11:29 PM
Of course, since you use three dimensional space. I believe the Four Color Theorem assumes a single plane. If you could create a map in two dimensions then I'd be impressed.

Zach L.
05-15-2004, 07:13 AM
That was my point. It is easy if you change the assumptions, and probably impossible if you don't. :)

Perspective
05-15-2004, 08:04 AM
alright, ill take a shot at it.

*note: black region counts as a region that needs to be coloured. I guess i could have used orange or something :rolleyes:

anonytmouse
05-15-2004, 09:09 AM
Change the inner black to blue and the outer black to yellow.

http://www.math.gatech.edu/~thomas/FC/fourcolor.html
The next major contribution came from Birkhoff whose work allowed Franklin in 1922 to prove that the four color conjecture is true for maps with at most 25 regions.

So if you want to 'solve' it maybe you should try using more than 25 regions.

scrappy
05-15-2004, 04:05 PM

Glirk Dient
05-15-2004, 04:24 PM
color red gree and and the middle and outside red.

anonytmouse
05-15-2004, 04:48 PM
Back to kindergarten.

ZerOrDie
05-15-2004, 07:04 PM
>>Can anyone prove me wrong?

LOL...pft, why would we prove you wrong, if you didn't come up with that.

BTW, in my data structures and discrete math class, our prof said he will give out an A for the course if anyone can prove the theroem wrong...

I bet he would seeing as it would make your prof instantly famous. No one has proved or disproved the theorem for a map of more than 25 regions. The proof published by Appel-Haken is not accepted and will not be accepted for a couple reasons.

1). Parts are done on computers and cannot be verified by hand.
2). No one has been able to check the rest of the proof in it's entirety.

Glirk Dient
05-15-2004, 11:15 PM
Can anyone link to a site that says in the theorem the regions cannot touch at a point? I searched and didnt find anything about that.

If no one can I will continue to think I am the winner so I feel special.

XSquared
05-15-2004, 11:24 PM
The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color.

http://mathworld.wolfram.com/Four-ColorTheorem.html

Glirk Dient
05-16-2004, 09:34 AM
Awwww....

Dissata
05-16-2004, 02:28 PM

XSquared
05-16-2004, 05:23 PM
Change all of the dark green ones to light green and then you can colour the black part dark green.

Xterria
05-16-2004, 05:30 PM

grib
05-16-2004, 05:58 PM
Exchange either yellow and red vertically and color the square yellow or red.

Xterria
05-16-2004, 06:42 PM
actually theres another way of doing it but that works too

Dissata
05-16-2004, 09:16 PM