Reply to comment
Do five suffice? This is a hint
The problem becomes easier to deal with when you represent each country by a coloured dot and connect two dots by a line if the corresponding countries are neighbours. This gives you what is called a graph. An important property of this graph is that, because it comes from a map, no two lines in it cross each other.
Now look at the dots representing the new country's five neighbours and label them 1, 2, 3, 4, and 5 in cyclical order. What can stop you from recolouring dot 3 with the colour of dot 1? And what does that mean for the other dots?