If a map is drawn such that each point on the boundary of a region is surrounded by an even number of regions then the map can be coloured in two colours.

That means that two colours are sufficient to colour such a map so that no two regions that share a common border are coloured with the same colour.

Proof:

Consider any region, label it 0. Now consider any region bordering this region, label it 1. Continue labelling regions so that the label indicates the least number of steps required to pass from the region labelled 0 to that region.

All regions bordering a region labelled n will be labelled either n - 1 or n + 1. If two regions labelled 1 are neighbours then their corner point on the border with region labelled 0 will have an odd number of regions surrounding it. Similarly, if two regions labelled n are neighbours then their corner point on the boundary with the region labelled n - 1 will have an odd number of regions surounding it. Therefore two regions with the same label cannot be neighbours. So regions with an odd label can be coloured in one colour and regions with an even label can be coloured with the other.

The theorem is equivalent to stating that all maps drawn with only infinite lines or closed loops are two colourable.

A proof by induction could be formed using this induction step:

See Four Colour Theorem
Last change to this page
Full Page history
Links to this page
 Edit this page
  (with sufficient authority)
Change password
 Recent changes
All pages
Search