Find the chromatic polynomials to this graph

Question

The numbers $1$ to $5$ are name of the each vertex.

What is the chromatic polynomial for this graph?

I tried have tried using the deletion contraction theorem but when I do that I get a different result each time.

Answer 1

This is the wheel graph on $4$ spokes, and so needs at least $3$ colours. Let the hub, vertex $2$, have any one of $n$ colours, then the remaining vertices may be coloured using four, three or two other colours. Cases follow:

• If all the four spoke vertices have different colours, there are $(n-1)(n-2)(n-3)(n-4)$ ways to colour them.
• If three colours are used for the spokes, one colour must be duplicated and the vertices of that colour must be diametrically opposite. Those vertices may be placed in two orientations, leading to $2(n-1)(n-2)(n-3)$ ways.
• If only two colours are used, they must alternate around the wheel, but otherwise there are no restrictions – $(n-1)(n-2)$ ways.

Thus the chromatic polynomial for this graph is $n(n-1)(n-2)((n-3)(n-4)+2(n-3)+1)$ or $n(n-1)(n-2)(n^2-5n+7)$.