= Solution
An <inclusion-exclusion principle>[inclusion-exclusion] proof gives the coefficients directly. For an <edge> set $F\subseteq E(G)$, let $c(F)$ be the number of connected components of the spanning <graph> $(V(G),F)$, including isolated vertices. Requiring the two endpoints of every <edge> of $F$ to have the same colour leaves exactly $x^{c(F)}$ colourings. Thus the <chromatic polynomial inclusion-exclusion formula> is
$$
p_G(x)=\sum_{F\subseteq E(G)}(-1)^{|F|}x^{c(F)}.
$$
Consider a term with $n-c(F)=i\leq k-2$. If $(V(G),F)$ contained a <cycle>, that <cycle> would have length at least $k$. The component containing it would have at least $k$ vertices and hence contribute at least $k-1$ to $n-c(F)$, a contradiction. Therefore $F$ is a <forest>. For a <forest>, $n-c(F)=|F|$, so necessarily $|F|=i$.
Conversely, every $i$-element <edge> set with $i\leq k-2$ is a <forest>, since a <cycle> would require at least $k$ edges. Thus exactly $\binom mi$ <edge> sets contribute to the coefficient of $x^{n-i}$, and they all have sign $(-1)^i$. Consequently
$$
\boxed{a_i=\binom mi\qquad(0\leq i\leq\min(k-2,n-1)).}
$$
This proves <girth determines initial chromatic coefficients> without requiring the suggested double <induction>.
Back to article page
