display | more...

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.