display | more...

This is a technique for re-colouring a cubic map so as to enable, at most, five colours be used to fill the entire map. It is used in proving the Five colour theorem, and was, for a long time, the reason behind an incorrect proof of the Four colour theorem.

Alfred Bray Kempe was a student under Arthur Cayley whilst at Cambridge university. AS a result, he attended a meeting of the London Mathematical Society, where Cayley raised a question on the Four colour theorem. By June of the same year, 1879, Kempe had published what he believed to be a complete proof.

The basic concept is a method for re-colouring the neighbours of a four-, or five-sided country. It is clear that, in either case, it is quite possible for the neighbours of such countries to use up all of the available colours, leaving the central country without a colour.

For example, given the colours; red, blue, yellow and green:

       \     R     /
        \         /
         o-------o
     G   |   ?   |   B
         |       |
         o-------o
        /         \
       /     Y     \

Kempe's technique was to pick two of the surrounding colours that are not themselves neighbouring, and look at all countries of those colours. Using a simple example, lets look at red and yellow.

    -----o------o-----o
        /        \  Y  \
   \   o    R     o    o---o
    \ / \        / \  / R /
     o   o------o   o   o
     | G |  ?   | B  \ / \
     |   |      |    _o   \
  ---o   o------o   /   Y  \
      \ /   Y    \ o---o---o---
       o--o---o---o   /
         /     \  R  /
        /       o---o

Ignoring the green and blue countries, you can see that there is a chain of red/yellow countries that connect the red one above the square, to the yellow one below the square. This an example of the eponymous chain. This chain means that it is impossible for the green and blue neighbours to be linked by a similar chain. So, we are able to re-colour either of these countries. For example, we could re-colour the blue country green, which would then allow us to colour the central square blue.

There is a one other case to consider:

    -----o------o-----o
        /        \  Y  \
   \   o    R     o    o---o
    \ / \        / \  / G /
     o   o------o   o   o
     | G |  ?   | B  \ / \
     |   |      |    _o   \
  ---o   o------o   /   Y  \
      \ /   Y    \ o---o---o---
       o--o---o---o   /
         /     \  R  /
        /       o---o

In this example, the top right red has been changed to green. This means that there is no longer a Kempe chain connecting the red and yellow neighbours. We can now use the same argument as we used for the blue-green countries in the previous case. As the red-yellow countries are not connected, we can safely re-colour one of them to free up a colour to use in the central square.

Although worked through here using a central square, Kempe believed the same method could be used for a central pentagon. As such, he believed he had found the proof for the Four colour theorem. The outline of which was:

  • By the Five neighbour theorem, (a result Kempe successfuly achieved himself), we know that there is at least one country with five neighbours or fewer.
  • Identify said country and collapse to it a single vertex.
  • Repeat this until only a single country remains.
  • Colour the single country with any of the four colours.
  • Restore each collapsed country, in reverse order, colouring it appropriately.
It was in the last step here that his chains were so useful.

He duly published the proof, and had to wait 11 years for anyone to spot his mistake. This was done by Percy John Heawood, a lecture at Durham University. Heawood produced a map that could be coloured using four colours, but could not be done using Kempe's technique. The flaw Heawood demonstrated was that it is possible for a central pentagon to require multiple colour changes which cause conflict elsewhere on the map. However, this only applies when the colour limit is four. Using Kempe's ideas, Heawood was able to prove the Five colour theorem.

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