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.