I am learning about graph coloring. One of the exercise problems(grimaldi) led me to derive the chromatic polynomial for any cycle($C_n, n \ge 3$).
$P(C_n, \lambda) = (\lambda - 1)^n + (-1)^n(\lambda - 1)$, where $\lambda$ is the number of colours available
Is it possible to interpret the terms of above polynomial? I need help doing the same.
There is a theorem of Whitney answering your question. Let $$ P(G,\lambda) = \sum_{k=0}^n (-1)^k a_k \lambda^{n-k}. $$ Then $a_k$ is the number of $k$-subsets of the edges of $G$ not containing any broken cycle. A broken cycle of $G$ is obtained from a cycle of $G$ by removing its maximum edge according to some fixed ordering of the edges.
For example, if $G = C_n$ then for $k < n-1$, $a_k = \binom{n}{k}$, and $a_{n-1} = \binom{n}{n-1} - 1$, since we miss one broken cycle.
For a proof and references to other proofs, see this paper.
