Peter Schmuecking, a 41 year old male from Roetgen nr Aachen/Germany asks on February 3, 2002,

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

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.

Note: All submissions are moderated prior to posting.

If you found this answer useful, please consider making a small donation to science.ca.

- Canadian Nuclear Safety Commission Educational Resources
- National Inventors Hall of Fame
- JUMP Math
- Society for Canadian Women in Science and Technology
- SciQuest e-Solutions for Science
- Natural Sciences and Engineering Research Council of Canada
- Manning Awards for Innovation
- Royal Society of Canada
- Geological Survey of Canada
- Canadian Networks of Centres of Excellence
- Canadian Landscapes at Natural Resources Canada
- Canadian Association of Physicists
- A Century of Innovation
- Understanding Science
- AlphaGalileo
- National Film Board of Canada Youth Science
- PICS Climate Insights 101
- Canadian Association for Girls in Science
- Virtual Library for the History of Science
- The Chemical Institute of Canada
- Canadian Biotechnologist 2.0
- ISI Highly Cited Scientists
- Deep River Science Academy
- Journal of the History of Canadian Science
- Wikipedia
- Innovation Canada
- Mars Society
- Nobel Prize Archive
- science.gc.ca
- Online Science & Engineering Encyclopedia
- CurioCity
- Canadian Nuclear FAQ
- Association of Science Communicators
- Astrofiles
- Wilderness Astronomy