B6. The diagram shows five circles connected by five line segments. Three colours are available to colour these circles. In how many different ways is it possible to colour all five circles so that circles which are connected by a line segment are coloured differently?
Solution
We first look at the number of different ways of colouring the four circles at the corners of the square.
If circles $B$ and $D$ are given the same colour, then they may be coloured in three different ways. For each of these, two colours are available for both circle $A$ and circle $C$. Therefore, if $B$ and $D$ have the same colour, then the four corner squares may be coloured in $3 \times 2 \times 2=12$ different ways.

If circles $B$ and $D$ are coloured differently, then we can choose three colours for $B$ and, for each of these, two different colours are available for $D$. So $B$ and $D$ may then be coloured in $2 \times 3=6$ different ways. Now, however, only one colour is available for circles $A$ and $C$, so if circles $B$ and $D$ are coloured differently then there are six ways of colouring the corner circles. Hence in total the four corner circles may be coloured in $12+6=18$ different ways. For each of these 18 possibilities, circle $E$ must be coloured differently from circle $C$ and thus two colours are available for it. Therefore, in total, there are $2 \times 18=36$ different ways of colouring the five circles so that connected circles are coloured differently.