How to obtain the chromatic polynomial of $C_5$? I've been reading some books on chromatic polynomials, I am a little confused at the procedure that is needed to obtain it. I've read in a book that the chromatic polynomial is obtained by partitioning $V$ in independent sets, if we have $f(r)$ ways to do this partition, then we have in general:
$$P(G,\lambda)=\sum^n_{r=1}P(K_r,\lambda)f(r)$$
because if we contract each independence in a unique vertex, we'll obtain a clique $K_r$.
It's not really clear what I should do. In the case of $C_5$, I guess I should partition it on all possible independent sets, but it's not really clear how I should obtain $f(r)$.
 A: In fact, the chromatic polynomial $P(G,\lambda)$ gives the number of partitions of the vertex set of $G$ into $\lambda$ independent sets (for integer $\lambda \geq 0$), aka, the number of proper colorings.  (I don't understand the formula given; perhaps the summand should be $\lambda^{f(r)}$?.)
It might be possible to deduce the polynomial from counting partitions, but it's not a natural (or easy) way of computing the chromatic polynomial of $C_5$.  It's easier to use the addition/identification or deletion/contraction relations.
If we use deletion/contraction on $C_5$, we get:
\begin{align*}
P(C_5,\lambda) &= P(P_4,\lambda)-P(C_4,\lambda) \\
 &= \lambda(\lambda-1)^4-P(C_4,\lambda)
\end{align*}
(we can find the chromatic polynomial of the $4$-edge path $P_4$ via combinatorics: $\lambda$ colors to choose from for the first vertex, and $\lambda-1$ colors to choose from for each remaining vertex) and
\begin{align*}
P(C_4,\lambda) &= P(P_3,\lambda)-P(C_3,\lambda) \\
 &= \lambda(\lambda-1)^3-\lambda(\lambda-1)(\lambda-2)
\end{align*}
(we can similarly find the chromatic polynomial of the complete graph $K_3=C_3$ combinatorially).
Combining these gives:
\begin{align*}
P(C_5,\lambda) &= \lambda(\lambda-1)^4-\lambda(\lambda-1)^3+\lambda(\lambda-1)(\lambda-2) \\
 &= \lambda^5-5\lambda^4+10\lambda^3-10\lambda^2+4\lambda.
\end{align*}
It's also possible to prove that the chromatic polynomial of a cycle $C_n$ is $(\lambda-1)^n+(-1)^n(\lambda-1)$ (e.g. see this math.SE question)
A: Another possible way to find the chromatic polynomial is to use basic counting methods working from the definition. $P(C_5,\lambda)$ is defined to be the number of ways to color the vertices of $C_5$ in $\lambda$ colors so that adjacent vertices do not receive the same color. Let the vertices of the cycle be $v_1$, $v_2$, $v_3$, $v_4$, $v_5$ in that cyclic order. Pick a color for $v_1$ in $\lambda$ ways. Now $v_2$ and $v_5$ cannot have the same color as $v_1$, so there are $\lambda - 1$ choices of color for each of them. Split into two cases:


*

*$v_2$ and $v_5$ receive the same color in $\lambda - 1$ ways. Then $v_3$ cannot receive the same color as $v_2$, and has $\lambda - 1$ choices of color, and finally $v_4$ cannot receive the same color as $v_3$ or $v_5$, which are colored with different colors, so there are $\lambda -2$ ways to color $v_4$. So this case accounts for $\lambda (\lambda -1)^2 (\lambda - 2)$ colorings.

*$v_2$ and $v_5$ receive different colors, so there are $\lambda - 1$ choices for $v_2$ and then $\lambda - 2$ choices for $v_5$. Now $v_3$ cannot receive the same color as $v_2$, so we have $\lambda -1$ choices for $v_3$. In $1$ of those cases, $v_3$ receives the same color as $v_5$, and we have $\lambda - 1$ choices of color for $v_4$. In the remaining $\lambda - 2$ cases, $v_3$ recieves a different color than $v_5$, and we have $\lambda - 2$ choices of color for $v_5$. So this case accounts for $\lambda (\lambda -1)(\lambda -2)((\lambda -1) + (\lambda -2)(\lambda-2))$ colorings.
So the total number of colorings is:
\begin{array} \\
P(C_5, \lambda) &= \lambda (\lambda -1)^2 (\lambda - 2) + \lambda (\lambda -1)(\lambda -2)((\lambda -1) + (\lambda-2)^2) \\
&= \lambda (\lambda -1) (\lambda - 2)((\lambda - 1) + (\lambda -1) + (\lambda -2)^2) \\
&= \lambda (\lambda -1) (\lambda - 2)(\lambda^2 - 2\lambda + 2) \\
&= \lambda^5 - 5\lambda^4 + 10 \lambda^3 - 10 \lambda^2 + 4 \lambda
\end{array}
