Every map can be coloured with six colours such that no neighbouring countries have the same colour.

This is a theorem that is closly related to the more famous four color theorem, although is notably weaker. The proof of this theorem is much easier than for its four-coloured cousin.

Using proof by contradiction, we are going to assume that there exists a minimal map that with the fewest possible countries, requires 7 colours; all maps with fewer countries can be coloured using 6 colours.

Using the Five Neighbour theorem, we know that any such minimal map must contain a country with at most five neighbours. In other words, it must contain either a two-sided contry (a 'diagon'?), triangle, square or pentagon. We need to consider each of these cases and show that because they exist in a map, that map cannot be a minimal map - and as such, a minimal map cannot possibly exist at all.

To begin with, we shall consider the pentagon.

```            |
|
1     o     2
/   \
/       \
-----o    6    o-----
\       /
5    o-----o    3
/   4   \
/         \
```

If we remove one of the boundaries of this country we are left with a map that has one country less than the minimal map. By our original statement, we must be able to colour this new map using six colours.

```            |
|
R     o     G
\
\
-----o         o-----
\       /
P    o-----o    B
/       \
/    Y    \
```

Once this is done, if the boundary that was removed is reinstated, we have a coloured map with a blank country. This blank country has five neighbours and therefore it has five colours neighbouring it. This leaves us with the sixth colour to complete the map.

```            |
|
R     o     G
/   \
/       \
-----o    I    o-----
\       /
P    o-----o    B
/       \
/    Y    \
```

It has not been necessary to use the seventh colour at all. This means that the map that we claimed to be minimal, which contains a pentagon, is not infact a minimal map.

Using the same argument, we can also show that none of the other 'required' shapes can exist in the minimal map. Therefore, a minimal map that requires 7 colours cannot exist.

The next step from here is to show that no more than 5 colours are required.

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