The whole reason for the exercize is in order to print maps with the fewest colors (least printing costs)
You dont want the same color for any two countries that touch each other (like canada and mexico can both be green, but not US and mexico)
It is ALWAYS possible to do with 4 colors or less
..or less?