# 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.

*If you found this answer useful, please consider*

making a small donation to science.ca.

making a small donation to science.ca.