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 14303 times

the answer

Aaron Abrams answered on February 4, 2002, A:

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.

Add to or comment on this answer using the form below.
(required)
(required if you would like a response)
Note: All submissions are moderated prior to posting.
If you found this answer useful, please consider making a small donation to science.ca.