Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The four color map?

  1. Mar 29, 2008 #1
    [SOLVED] The four color map??

    so i guess most of you know about the four color map theorm.

    i read about it in a book a couple of days ago and had some idle brain time today while driving a tractor.
    i scribbled out some maps on the dirt on the windows and always seems to enclose one region of the map in my attempt to find a five color map.

    i then reasoned that if a five color map existed then there must be a section of it containing 5 mutually adjoining regions. and that if i could stand in any one of the regions i should be able to walk to any of the other four without crossing another. and so i thought.. i'll draw dots to represent regions and lines to represent the path i'd take from one to another. so in joining the dots i again come to a stop, it is impossible for me to join all dots to all dots without crossing lines, i.e. distroying boarders between regions. so i thought, i'll draw another five dots and this time be carefull not to cross lines, but i end up in a situation where in order to connect two dots i must enclose a "deficient" dot.

    so i figure there can never exist 5 mutally adjoining regions unless i can connect all the dots without crossing lines. if there and only 4 mutally adjoining regions [which can be easily done with dots and lines] i only need 4 colours.

    i then wonder, does the orientations of the dots matter?, and i think, no, because i can alter my path,
    i then wonder does it matter what order i connect the dots in, and i think, perhaps, but if the orientation of the dots isnt important then they may as well be points on a circle and so be very symetrical, so the order wont be too important

    then i feel very happy that i will no longer waste my time trying to draw a five color map on the side of a trailer or the inside of a tractor cab. i've satisfied myself it cannot be done. then i wonder,.. does that consititute a proof.

    so i do some googleing and find that some equally clever people have already done pretty much the same thing. but they dont call it proof??

    so i'm figureing, i'm satisfied i cannot connect all the 5 dots, but i havnt "prooved" it. it's pretty obvious to someone who tries they cannot do it. [much more obvious than trying to draw funny maps!!) so why is it not accepted as a proof?? or has anyone any thougths on this

    apologies as always for my spelling
  2. jcsd
  3. Mar 29, 2008 #2


    User Avatar
    Science Advisor

    I don't know why it wouldn't be called a proof. Appel and Haken proved that in 1976.
  4. Mar 29, 2008 #3


    User Avatar
    Science Advisor
    Homework Helper

    Trying as many cases as you can think of isn't a proof - if there is an infinite number of cases to try.
    What I remember being proved is that all maps can be split it one of a large (but finite) number of examples and then they 'proved' on a computer that all of these maps were 4 colour.
  5. Mar 30, 2008 #4
    This is not enough for a proof. There are maps that you can't colour with 4 colours, that do not contain 4 mutually adjoining regions.
  6. Mar 30, 2008 #5
    thanks guys i suppose that would explain why its not a solution!!
    i'd be interested to see the map you refer to!!
  7. Mar 30, 2008 #6
    I'm sure you must have seen a map like that many times. Any map with an area that is surrounded by a ring of an odd number of areas needs four colours. For example Nevada and the five states surrounding it.
  8. Mar 30, 2008 #7
    i see.. i've just done it!!
    interesting how adding, or removing one region will reduce it to a 3 color map!
    [never seen a map of nevada!!]
  9. Mar 31, 2008 #8


    User Avatar
    Science Advisor

    I think you mean "There are maps that you can colour with 4 colours".
  10. Mar 31, 2008 #9


    User Avatar
    Science Advisor
    Homework Helper

    I thought kamerling meant, "There are maps you can't color with 3 colors.".
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook