Every map in which all points on country borders are surrounded by an even
number of countries can be coloured with two colours. (Note: no special surfaces. Sea, etc. is a country, too.)
Proof: consider any country c on such a map. Now consider for any number n the set D(n) of countries at distance n from c. That is, a country is in D(n) iff it can be reached from c in n steps and no fewer.
For n=0, the set consists of the country itself. For n>1, all neighbours of countries in D(n) are either in D(n-1) or D(n+1); if two countries in D(n) were neighbours, their corner point at the D(n-1) borderline would be surrounded by an odd number of countries! Therefore, we can colour D(n) in c's colour if n is even, and in the other colour if n is odd.
Attempts to extend this proof to the four color theorem have turned out to be nontrivial.