You need just four colors to fill any realms in your flat spaces. This is called Four color theorem.
You prove it by induction.
At first, there are 3 countries in your map. You can add the one color.
There is the rule which must be the different color when they face each other. Therefore, yellow is acceptable.
Then, you have 4 countries in your map. Do you need 5 colors to fill your space?
This is complicated, and you need to choose the color to adjust the Four color theorem.
You don't need 5 colors.
Is this induction satisfied with any situation?
This is beyond our ability. The Four color theorem seems to be correct, but we rely on the computer.