Only 4 are used!

This is a discussion on Only 4 are used! within the A Brief History of Cprogramming.com forums, part of the Community Boards category; You can color any map using only four or less colors! I can't remember the name of the guy who ...

  1. #1
    Caffienated jinx's Avatar
    Join Date
    Oct 2001
    Posts
    235

    Only 4 are used!

    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).
    Weeel, itss aboot tieme wee goo back too Canada, eeehy boyss.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,823
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    >>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...

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  4. #4
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    >> Can anyone prove me wrong?
    Given a satisfactory set of axioms, quite easily.

  5. #5
    RoD
    RoD is offline
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331
    >>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.

  6. #6
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    try coloring this map with only 4 colors....

    (yes the land formation is completely unrealistic, but still!)
    Attached Images Attached Images  
    My Website

    "Circular logic is good because it is."

  7. #7
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Quote Originally Posted by DavidP
    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.

  8. #8
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Or if you wanted to fill in every area:
    Attached Images Attached Images  

  9. #9
    Registered User
    Join Date
    Jan 2003
    Posts
    361
    What about a square divided into 4 equal parts(4 smaller squares) and completely surrounded by the same land.

  10. #10
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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.
    Attached Images Attached Images  

  11. #11
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    echo Glirk Dient and Zach L.
    My Website

    "Circular logic is good because it is."

  12. #12
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    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
    Attached Images Attached Images  
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  13. #13
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    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?

  14. #14
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    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.
    My Website

    "Circular logic is good because it is."

  15. #15
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Quote Originally Posted by DavidP
    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!

    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.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21