= Solution
Induct using the same <deletion-contraction recurrence for the chromatic polynomial>. The edgeless <graph> has <polynomial> $x^n$, so its leading coefficient is one and the others are zero. All nonempty-vertex chromatic polynomials have zero constant term, since no coloring uses zero colors.
For an existing edge, write the alternating coefficient lists of the deletion and simplified contraction as $a_i'$ and $a_i''$. The contraction has $n-1$ vertices, so subtracting its <polynomial> changes its leading sign by one place. Thus
$$
a_i(G)=a_i'+a_{i-1}'',
$$
with nonexistent indices understood as zero. Both summands are nonnegative by <induction>. The leading coefficient is $a_0=1$, and the next is
$$
a_1=(m-1)+1=m.
$$
This proves the alternating expansion and \b[nonnegativity of every $a_i$]. The coefficient assertion for $a_1$ is relevant when $n\geq2$; the one-vertex <graph> simply has <polynomial> $x$.
Back to article page
