In order to colour adjacent countries on a world map in different colours, you'd need at minimum only 4 different colours! Or in other words, no two countries in the world share more than 3 borders with the same border countries (including each other)