The purpose of this investigation is to explore what the minimum number of colours is needed to colour in a map so that no two adjacent countries share the same colour. In this case, adjacent countries share a border of more than a point.
Students can start off with a standard map, like a Map of Africa, and begin by experimenting to see what colours work on this map. They could then move to creating their own non-standard maps, and seeing if the minimum still holds. They can also try and investigate what special maps (and their properties) lead to maps that can be shaded with 1, 2, or 3 colours.
The answer to this question is well known, but you should lead students to try and answer a less well known question, why does it work?
Aside: The easiest way I’ve found to actually have students work on this is to download a blank copy of the map of Africa (with the country borders included) and let them use MS Paint (or any other software that works) and let them shade in countries with the program.