= Solution
Induct on the number of edges, allowing coefficients outside the displayed degree range to be zero. An edgeless <graph> has $p_G(x)=x^n$, so its leading coefficient is $1$ and all others are zero. For an <edge> $e$, write the alternating coefficients of $G-e$ as $b_i$ and those of the simplified contraction $G/e$ as $c_i$. The <deletion-contraction recurrence for the chromatic polynomial> gives
$$
p_G(x)=\sum_i(-1)^ib_i x^{n-i}-\sum_j(-1)^jc_j x^{n-1-j}
=\sum_i(-1)^i(b_i+c_{i-1})x^{n-i},
$$
with $c_{-1}=0$. Both smaller graphs have fewer edges, so <induction> gives nonnegative coefficients $b_i,c_i$. Thus $a_i=b_i+c_{i-1}\geq0$. Moreover $a_0=b_0=1$ and
$$
a_1=b_1+c_0=(m-1)+1=m.
$$
For a <graph> with at least one <vertex>, $p_G(0)=0$, so the constant term vanishes. Therefore
$$
\boxed{p_G(x)=\sum_{i=0}^{n-1}(-1)^ia_i x^{n-i},\quad a_0=1,\quad a_1=m,\quad a_i\geq0.}
$$
In the one-<vertex> case, the coefficient of $x^{n-1}$ is simply zero; this is the same $a_1=m=0$ convention beyond the written summation range.
Back to article page
