Neither is the North Sea! Nonetheless, this is a neat example.
> Back to my original question: does anybody know of a valid counterexample for the statement on countries?
A standard counterexample to the hypotheses of the 4-colour theorem (though not to the conclusion, as consulting a map easily verifies) is Michigan, which is not connected.
The 4-colour theorem's hypotheses also rules out the possibility of 4 countries meeting at a corner (or, rather, declare that they don't meet in that case). If there were such an arrangement—and I'd be surprised if there isn't; for 3 countries, one has the example of Finland, Sweden, and Norway—then it would be easy to juice it up to a counterexample.
Maybe the guy who established an island with a bizarre currency, including one coin that had a denomination of π (I can't remember who—I thought Dean Kamen, but his Wikipedia page doesn't mention it), could be induced to subdivide his island in such a way as to create a counterexample. :-)
