# Chromatic polynomial of a graph $G$

Let $G$ be the graph in picture: calculate the chromatic polynomial of it.

My attempt:

I assume that $G(K_n,x)$ is the number of distinct colors of the complete graph with $n\geq1$ vertices with at most $x$ colors. So, in case of a classic square it'll be:

$G(K_4,x) = x(x-1)(x-2)(x-3) = x^4-6x^3+11x^2-6x$

but here we have one more edge between two nodes. What should I do?

• You mention a square, which is different from $K_4$. You have one fewer edge than $K_4$, not one more. – Théophile Aug 19 '14 at 17:13

Consider coloring the vertices one at a time, with $x$ colors. Beginning with the upper left vertex, you have $x$ choices of color for that vertex. Once that color is chosen, there are $x-1$ choices of color for the lower left vertex (it cannot have the same color as the upper left vertex). Once those colors are chosen, there are $x-2$ choices of color for the upper right vertex (it cannot have the same color as the upper left or lower left). Finally, there are $x-2$ choices for the lower right vertex (it cannot have the same color as the lower left or upper right). So we have:
$$\chi(G,x) = x(x-1)(x-2)^2 = x^4 - 5x^3 + 8x^2 - 4x$$