= Solution
{c}
Write $V=V(G)$ and $E=E(G)$. For $F\subseteq E$, let $c(F)$ denote the number of <connected components of a graph> of the spanning <subgraph> $(V,F)$, including isolated <vertices>. The <inclusion-exclusion principle>, applied to the unwanted events that the two endpoints of an <edge> receive the same colour, gives the <chromatic polynomial inclusion-exclusion formula>
$$
p_G(x)=\sum_{F\subseteq E}(-1)^{|F|}x^{c(F)}.
$$
To justify the exponent, imposing equal colours across all <edges> in $F$ forces a single colour on each <connected component of a graph> of $(V,F)$, with independent choices between its <connected components of a graph>. Thus the corresponding count at $q$ colours is $q^{c(F)}$. Equality for all positive <integers> proves the <polynomial identity>.
Fix an index $i$ in the stated range. A <subset> $F$ contributes to the coefficient of $x^{n-i}$ exactly when $n-c(F)=i$. If $(V,F)$ contains a <graph cycle> of length $s$, the hypothesis gives $s\geq\ell$. All its $s$ <vertices> lie in one <connected component of a graph>. For any <connected component of a graph> $D$, its contribution to $n-c(F)$ is $|V(D)|-1$, so
$$
n-c(F)=\sum_D(|V(D)|-1)\geq s-1\geq\ell-1.
$$
This contradicts $i\leq\ell-2$. Therefore every contributing $(V,F)$ is a <forest>. The <forest> identity $|F|=n-c(F)$ then gives $|F|=i$.
Conversely, every $i$-<edge> <subset> is a <forest>, since a <graph cycle> in it would have at most $i<\ell$ <edges>. It therefore has $c(F)=n-i$ and contributes exactly $(-1)^i$. There are $\binom mi$ such <subsets>, by the definition of a <binomial coefficient>. Consequently
$$
[x^{n-i}]p_G(x)=(-1)^i\binom mi,\qquad
\boxed{a_i=\binom mi\quad(0\leq i\leq\ell-2).}
$$
Here the coefficient notation is understood within the defined indices $0\leq i\leq n$; if the displayed range is extended past $n$, the coefficients beyond the constant term can be set to zero. For a <forest>, $m\leq n-1$, so the <binomial coefficients> there are also zero. The key reason <girth determines initial chromatic coefficients> is that a <graph cycle> can affect only exponents whose loss of <connected components of a graph> is at least $\ell-1$.
Back to article page
