Possible ways to color vertices

Question

Considering a graph formed by $4$ verticles connected between them (like it's a circle). Having available $3$ distinct colors, in how many ways is it possible to color the verticles of the graph giving different colors to adjacent verticles?

So $v_1$ is connected to $v_2$ and $v_4$; and $v_3$ is connect to $v_2$ and $v_4$.

My textbook says that the possible ways are $18$ but I don't understand why. Aren't they $$ 3\cdot 2\cdot 2\cdot1 = 12? $$

Answer 1

Colour in two opposite vertices first.

• If those vertices receive the same colour (3 ways), the other two vertices can independently be either of the other two colours ($2×2=4$ ways).
• If those vertices receive different colours ($3×2=6$ ways), the other two vertices must be the third colour.

This gives $3×4+6=18$ ways.

Answer 2

Your equation is wrong, I assume you were thinking that $v_1$ can be coloured $3$ different ways then for the neighbouring vertices ($v_2$ and $v_4$) you could pick from $2$ different colours, hence the multiplication by $2\cdot 2$ and if you picked different colours for these vertices you will only have $1$ colour left for the last vertice $v_3$.

You could correct this in the following way:

Colour the first vertice some colour, you have $3$ choices and then you have to look at two cases

1) The neighbouring vertices has the same colour then you could pick this colour from the remaining $2$ colours and you have $2$ colours left for the last vertices (the colour of the first one or the one you did not choose for the second and the third). This gives a total of $2\cdot 2=4$ different colourings in this case

2) The neighbouring vertices are coloured differently, this can be done in two ways and in this case you have no choice for the last vertice giving only $2$ different possibilities

That is you have

$$ 3\cdot(4+2)=18 $$

ways to colour the graph according to the condition.