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.

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.

Log in or register to write something here or to contact authors.