= Solution
For an edge $e=uv$, colorings of $G-e$ divide into those giving $u,v$ different colors, counted by $p_G$, and those giving them the same color, counted by $p_{G/e}$. Parallel edges produced by contraction may be suppressed. Thus
$$
p_G(x)=p_{G-e}(x)-p_{G/e}(x).
$$
For an edgeless <graph> on $n\ge1$ vertices, $p_G=x^n$. Induct on the number of edges, allowing smaller vertex counts for contractions. If both smaller expansions have alternating nonnegative coefficients, the contraction's leading <degree> is one lower, so subtracting it gives
$$
a_i(G)=a_i(G-e)+a_{i-1}(G/e),
$$
with absent coefficients interpreted as zero. Each coefficient remains nonnegative. Both terms have zero constant coefficient for nonempty graphs, so the resulting expansion is
$$
\boxed{p_G(x)=\sum_{i=0}^{n-1}(-1)^ia_ix^{n-i},\qquad a_i\ge0}.
$$
This induction simultaneously proves the counting function is a polynomial.
Back to article page
