# Colouring in puzzle...

What is the minimum number of colours to make each adjacent vertex a different colour?

Solution

The graph has a 3-colouring; as shown in the diagram. The last thing to do is demonstrate that it doesn't have a 2-colouring. Fortunately, this is pretty easy. We can see that there exist cycles in the graph that link an odd number of vertices (for example, the pentagon in the top right hand corner). Since this cycle has 5 elements, then it can't be coloured with just two colours (you would always have two vertices adjacent to each other with the same colour). Therefore, there cannot be a 2-colouring, so $n=3$.