Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 3 / 17F / Solution

The chromatic polynomial $p_G(t)$ counts proper vertex colorings with $t$ labeled colors at positive integer $t$. For an edge $e$, the deletion-contraction recurrence for the chromatic polynomial is $p_G=p_{G-e}-p_{G/e}$, where parallel edges in the contracted graph are merged. Induction on edges, starting from the edgeless polynomial $t^n$, shows that the coefficients have alternating signs: the contracted graph has one fewer vertex, so subtracting its alternating polynomial reinforces the same signs. The leading coefficient stays one. The coefficient of $t^{n-1}$ decreases by one per added edge, hence it is $-m$. Thus $p_G(t)={\sum }_{i=0}^n(-1{)}^{n-i}{a}_i{t}^i$, with $a_n=1$, $a_{n-1}=m$ and all $a_i\ge 0$.

For a tree, choose a root, give it any of $t$ colors, and give every other vertex any of the $t-1$ colors different from its parent. This gives $p_G(t)=t(t-1{)}^{n-1}$. Conversely, a graph with this polynomial has $m=n-1$. The chromatic polynomial of a disjoint union is the product of those of its connected components, each divisible by $t$. The given polynomial has a simple zero at zero, forcing a single connected component. A connected graph with $n-1$ edges is a tree. The converse holds.

Finally the polynomial determines the number of vertices, the number of edges and the chromatic number. If it equals that of the Turán graph $T_r(n)$, with $1\le r\le n$, then $G$ has chromatic number $r$, so has no $K_{r+1}$, and has the maximum possible number of edges for such a graph. The equality case in Turán's theorem makes $G$ isomorphic to $T_r(n)$. This is the chromatic polynomial determines a Turán graph property. If $r>n$, the graph is simply complete and its edge count already determines it.