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.

-

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$.

-
The thing that has me confused is how I should handle the "negative" sign of the graph with the deleted edge with respect to the recurrence. – bill billerson Dec 13 '11 at 4:02
@bill: I'm afraid I don't follow you. Why are you putting "negative" in quotes? And what is there to handle? It sounds to me as if you're trying to apply this sign to the graph itself? The recurrence, and hence the sign, applies to numbers of colourings of graphs, not to graphs. If you have further questions about this, it might be best if you write out the recurrence you're trying to use. – joriki Dec 13 '11 at 4:10
Hm, I think my problem lies with the graph with the deleted edge. How should I be able to calculate this since it doesn't seem to come from the knowledge of the chromatic polynomial of $C_{n-1}$? Thanks for responding to my question, by the way. – bill billerson Dec 13 '11 at 4:24
@bill: A cycle with one edge deleted is a chain. In how many ways can you colour the vertex at one end of the chain? How many ways does that leave for the vertex adjacent to it? And how many ways does that leave for the vertex after that? And so on... – joriki Dec 13 '11 at 4:26

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-k)=(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.

-

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.

-