Conference rusure::math

>    Take a map of Europe and the adjacent countries and try to color
>    each country with a different color for each country .
>    What is the minimum number of colors that must be used ,such that
>    2 countries with a common boundary will always have a different
>    color ?

The vicinity of Luxembourg, surrounded by France, Germany, and Belgium, 
is an example of four being needed.
    
>    This can be solved easily by the "graph theory" but I'm curious
>    to know how it could be solved "mathematically" .

Easily? Proving that five are never required is extraordinarily difficult.
At any rate, I was under the impression that graph theory was subsumed in
mathematics. 

Lynn 

    
    Yes ,I get to the same conclusion. Four seems to be the minimum
    number of colors .
    
    When I say "it's easy to solve by the graph theory" ,maybe I should
    have said "it doesn't seem obvious to prove mathematically " or
    "it's easier to solve graphically".
    Does anybody see another approach to this "apparently" simple problem
    or to similar subjects ?         

The method that is used to solve problems of this type is called 
backtracking, and it amounts to directed trial-and-error. There is no 
direct algorithm to four-color a map (if there were, the very expensive
proof that five are never needed could be avoided) and the best method of
producing a two- or three-coloring of a map when that is possible is also
backtracking. 

Backtracking is an orderly method of looking for solutions of a problem 
from among a set that can be represented as a tree, and involves searching
along the branches of the tree until there is an indication that further 
search on the branch is futile, then backing up to a fork and continuing 
from there along another branch. To see how the tree arises in the map
problem, color one country, then an adjoining country, etc. until a fifth
color appears to be needed; then back up over the sequence of countries,
recoloring until only four are needed, etc. Since it has been proved that
five colors are never required, this process eventually terminates with a
correct four-coloring. 

    This is indeed a very difficult problem.  The four color conjecture
    was proposed a long time ago (over 100 years?), and only solved
    recently (about 10 years ago).  It was done at University of Illinois
    at Urbana-Champaign by Appel and Harken.  It was the first major
    mathematical theorem proved on a computer (taking over 1000 hours
    of computer time, I think).  When I was a grad. student in Illinois,
    I had a talk with Appel about the problem, and he told me that
    eventually they stopped counting how much computer money they used
    while doing the problem :-).  Because it is a computer proof, some
    mathematicians do not like it (no one ever read through that pile
    of mess :-).  The difficulty with that problem is that there are
    too many cases to be checked, and is humanly impossible to do them
    by hand (with the current method that is).   Recently, Appel (or
    one of his grad. student) is making an effort in putting that program
    on the Alliant Multiprocessor at Center for Supercomputer Research
    and Development of U of I.  I think they can expect some good speed
    ups since the problem consists of checking many independent cases.
    On the other hand, I do not see much point of doing it since one
    only needs to run the program once to do the job.
    Incidentally, Harken is a well known topologist and quite nice to
    have him around during parties (especially with some CH3CH2OH in
    him :-) :-).  He once came to a Holloween party of ours...).  
               
    Eugene
                                                     

    This question is one of the famous 'NP-complete' problems (that
    is, non-polynomially deterministic problems).
    
    It is typically refered to as the 'Four Colour Theory', where a
    planar graph does not require any more than 4 colours.
    
    It is true that this is an theory.  As mentioned in entryies .3
    and .4, the 'proof' of this was done on a CRAY computer, using the
    algorithm Lynn described in .3.  The  system tested all possible
    problems, within the timeframe the system was allowed to run.  Since
    it could NOT come up with a contradiction to the 4-Colour Theory,
    they assumed it was true.  Don't you wish you could have done that
    in University?   ;-)
    
    Anyway, the fact is that given a planar graph (such as the map of
    Europe), it will require at MOST 4 colours - proof clear!    :->
    
    
    Dave

    I believe it was run on a CDC machine -- a Cyber 6600 series running NOS,
    with the programming being done in Pascal.  The proof involves graph
    transformations that reduce the size of the 'map' without increasing
    the number of colors.  This reduces the problem to a small number of
    maps (100000?), which were colored by the program.  Also, I believe
    the names are spelled Appel and Haken.
    
    If someone else doesn't beat me to it, I'll dig up an article about the
    proof of the 4-color theorem, and will post something closer to truth
    than our fuzzy mis-remembrances.
    
    					- Gilbert
    
    P.S.  I was also at the UofI around then, and was friends with Dorthea
    Haken (Prof. Haken's daughter) who did some of the programming.

    As I remember, and I could be misremembering.  It was a bit less
    direct than this.
    
    The trick was to find a complete "basis" and prove that some graph
    theoretical property applied to all the elements of the basis. 
    If this property was true of all the elements of a complete basis
    than four-colorability was true for all graphs.  The basis was
    constructed in a fairly ad hoc way.  A certain amount of time
    was given to the program to prove the property for each element
    of the basis and if it hadn't succeeded by that amount of time
    the element was tossed out to be replaced by one or more alternatives
    which would be generated.  The 100000 element figure feels larger
    than I remember; 15000 feels closer to my impression of scale.
    100000 might be the total number of elements *considered* for the
    basis however.
    
    					Topher

>    It is true that this is an theory.  As mentioned in entryies .3
>    and .4, the 'proof' of this was done on a CRAY computer, using the
>    algorithm Lynn described in .3.  The  system tested all possible
>    problems, within the timeframe the system was allowed to run.  Since
>    it could NOT come up with a contradiction to the 4-Colour Theory,
>    they assumed it was true.  Don't you wish you could have done that
>    in University?   ;-)

The backtrack method will find a solution for a given map, but cannot be
used to prove that a solution exists for *all* maps. That depends on much
more sophisticated arguments. The Appel-Haken proof is indeed a proof, not
in the sense described above, which may be paraphrased as 'keep trying
until you get tired'. The proof was *complete*; they quit computing not 
because they ran out of time but because they exhausted the cases to test.

Lynn