display | more...

A cubic map is a collection of vertices, joined together by edges, to create enclosed faces, much like an ordinary map or graph. However, a cubic map has the added restriction that exactly three edges meet at vertex.

This type of map is of particular interest to people investigating the realm of map colouring, particularly when working with the four colour theorem.

You may be wondering why it is safe to restrict work on map colourings to just this sort of map. The answer to this was demonstrated by the mathematician Arthur Cayley in the April 1879 issue of the Proceedings of the Royal Geographical Society.

If we take a map that has a vertex with more than three edges meeting at it, we can add a new face over this vertex:

          \       /                     \       /
           \    /                        o----o
            \ /                        /      |
   --------- o ---------    =>   ----o        o-------
            / \                        \      |
           /    \                        o----o
         /        \                    /        \
        /           \                 /           \

The vertices of the new face all meet the requirement of having only 3 edges meet at them, and so it is now cubic. Once we have a colouring for the new cubic map, it is a trivial task of colouring the old map, as each new face can be simply shrunk back to the vertex they replaced.

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