I don't know how to draw graphs here, but my question is about rather simple graphs. First of all, consider the triangle graph, i.e the graph with 3 vertices and 3 edges that form a triangle. Now, vertex $a$ can be colored in $\lambda$ different ways (we have $\lambda$ different colors), but vertex $b$ in $\lambda -1$ different ways. The last vertex, $c$, can then be colored in $\lambda-2$ different ways. Hence the chromatic polynomial is $P=\lambda(\lambda-1)(\lambda-2)$. So far, so good.
However, now consider the square, i.e the graph $4$ vertices and $4$ edges that form a square. Vertex $a$ has $\lambda$ different colorings, $b$ has $\lambda-1$, vertex $c$ has also $\lambda-1$ but the last vertex, connected to both vertex $a$ and $c$ must have $\lambda-2$ different colorings. Hence, the chromatic polynomial $P=\lambda(\lambda-1)^2(\lambda-2)$. According to my book, the chromatic polynomial is $P=\lambda^4 -4\lambda^3+6\lambda^2-3\lambda$, and I simply can't see what mistake I have done, where is the fault in my reasoning?
Best Answer
Let the vertices of the 4-cycle be $(a,b,c,d)$ adjacent in the natural way. You correctly assumed that $a$ can be colored with $\lambda$ colors and there are $\lambda-1$ choices to color $a$ and $b$. But now you have to consider two cases. If $b$ and $c$ are colored with the same color there are actually $\lambda-1$ colors to color $d$. Can you take it from there?