Consider a
division of the
plane by
(a finite number of)* straight lines and
circles. Then the
condition of
rp's
writeup holds, so the resulting
map may be
coloured in
2 colours.
In fact, every map for which rp's condition holds is "topologically equivalent" to such a map. And we can prove the theorem in alternative manner for "my" maps.
For maps with 0 lines, the theorem is trivially true. Now suppose we want to add a line (straight or circle). We set a direction along the line, and flip the colours of all countries on its left. This transforms a legal 2-colouring of the map without the new line into a legal 2-colouring of the map with the new line. By induction, we see that such a map may be 2-coloured.
* Actually, all that's required is not to have an infinite number of segments in any closed bounded ("compact") domain. If you do, you haven't got a map you can meaningfully "colour", and it's uninteresting.