Prove that the chromatic polynomial of a cycle graph $C_{n}$ equals $(k-1)^{n} + (k-1)(-1)^{n}$ This is a homework question. But I am completely stuck.
My only intuition was to go about it inductively from a "greedy algorithm" maybe know as the deletion-contraction algorithm. And to somehow use the information about the jth cycle to solve the j+1th. But I'm not sure how I'd do it. Thank you very much for looking this over.
 A: You're on the right track. As far as I'm aware the greedy algorithm for finding a colouring and the deletion–contraction algorithm for counting them are two quite distinct algorithms. The deletion–contraction algorithm is exactly what you need. If you delete an edge in a cycle, the colourings of the remaining graph are straightforward to count, whereas if you contract an edge, you get a cycle with one fewer vertex. Thus you get a recurrence relation that expresses the number of colourings of $C_n$ as the number of colourings of $C_{n-1}$ plus a known expression. Then, since you already know the solution, you just have to verify that it solves this recurrence, and that it's correct for $n=2$.
A: You can also do this directly using the principle of inclusion–exclusion.  Label the vertices of $C_n$ sequentially using the integers $0$, $1$, ..., $n-1$.  For $S\subseteq\{0,1,\ldots,n-1\}$, let $T_S$ be the set of colorings (proper or improper) of $C_n$ in which, for each $j\in S$, the color of vertex $j$ is the same as that of vertex $j-1$ (with arithmetic performed mod $n$).  The number of proper colorings is then
$$
\lvert T_{\{\}}\rvert-\sum_{i=0}^{n-1}\lvert T_{\{i\}}\rvert+\sum_{0\le i<j<n}\lvert T_{\{i,j\}}\rvert-\ldots+(-1)^n\lvert T_{\{0,1,\ldots,n-1\}}\rvert.
$$
Now there are $\binom{n}{m}$ different $S$ of size $m$.  Furthermore,
$$
\lvert T_S\rvert=\begin{cases}k^{n-\lvert S\rvert} & \text{if $\lvert S\rvert<n$,}\\ k & \text{if $S=\{0,1,\ldots,n-1\}$.}\end{cases}
$$
Hence the number of proper colorings is
$$
(-1)^nk+\sum_{m=0}^{n-1}\binom{n}{m}k^{n-m}(-1)^m
$$
The result follows immediately from the binomial theorem.
A: Let's denote $P(G,k)$ be the chromatic polynomial of a simple graph $G$. By deletion-contraction formula, given any edge $e$ in $G$, we have the following: 
$$P(G,k)=P(G-e,k)-P(G\cdot e, k)$$
where $G-e$ is the graph obtained by deleting $e$ in $G$, and $G\cdot e$ is the graph obtained by contracting $e$ in $G$. 
To prove that $P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1)$, we use induction on $n$. For $n=3$, it's easy to see that we need to use different colors for different vertices. Therefore, $$P(C_3,k)=k(k-1)(k-2)=(k-1)(k^2-2k)=(k-1)^3+(-1)^3(k-1).$$ This proves the case when $n=3$. 
Now assume that $P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1)$. Apply the 
deletion-contraction formula to $G=C_{n+1}$, we have
$$P(C_{n+1},k)=P(C_{n+1}-e,k)-P(C_{n+1}\cdot e, k).$$
Note that the graph $C_{n+1}\cdot e$ is obtained by contracted an edge $e$ in $C_{n+1}$, which is isomorphic to $C_n$, which implies that 
$$P(C_{n+1}\cdot e, k)=P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1).$$
Note also that $C_{n+1}-e$ is the path $P_{n+1}$ with $n+1$ vertices, which implies that 
$$P(C_{n+1}-e, k)=P(P_{n+1},k)=k(k-1)^n.$$
(To see the last equality, we can use induction on number of vertices, or by simple counting argument: to color the end vertex, there are $k$ colors we can choose, then for the next one incident to the end vertex, there are $k-1$ colors we can choose, and so on.)
Combining all these, we have
$$P(C_{n+1},k)=P(C_{n+1}-e,k)-P(C_{n+1}\cdot e, k)$$
$$=k(k-1)^n-(k-1)^{n}-(-1)^{n}(k-1)=(k-1)^{n+1} + (-1)^{n+1}(k-1),$$
as required.
