mathematical and computing sciences question #636 Peter Schmuecking, a 41 year old male from Roetgen nr Aachen/Germany asks on February 3, 2002, Q:My son, 13 y, has found a really good idea to prove the four colour map problem without computers, but he needs support to answer a question for a topology math problem. My son says, when on any map there is a region that needs five colours then there is a way to draw a graph with 5 vertices and edges from any to any vertex without cutting each other. This is the point to prove: that this isn't possible. |
|
viewed 13327 times
|
the answer
Your son's idea of transforming a map into a graph is a good one. And he is correct that it is impossible to draw a complete graph on 5 vertices in the plane without any edges crossing.
Unfortunately, his other statement is not at all obvious, namely that a map requiring 5 colors would imply that you could draw the complete graph on 5 vertices without edges crossing. Indeed, no one has ever been able to prove this directly. What it does show is that you cannot have a map in which there are 5 countries with every pair sharing a border.
To perhaps clarify this further, he could try as an exercise to find a map which requires 4 colors (meaning you can't color it with 3), but in which there are no 4 countries which all share borders. In graph language, this means find a graph in the plane which requires 4 colors but which contains no complete graph on 4 vertices.
Or an easier one: find a graph that requires 3 colors but contains no complete graph on 3 vertices (i.e. triangles). (The easiest answer to this one is a pentagon, as your son will surely discover quickly.)
So you see, there may be a map which requires 5 colors, even though it contains no complete graph on 5 vertices. This is definitely one of the subtleties of the four-color problem.
Digg It!
making a small donation to science.ca.
