= Solution
Deletion-contraction also proves the alternating-sign form with nonnegative coefficients. If $G$ has $n$ vertices, $G/e$ has $n-1$, so subtracting its alternating expansion adds its coefficient at each succeeding index:
$$
a_i(G)=a_i(G-e)+a_{i-1}(G/e).
$$
Starting from an edgeless <graph> gives $a_0=1$ and no constant term when $n>0$.
For the first coefficients, inclusion-exclusion over the forbidden monochromatic edges gives the precise expression
$$
p_G(x)=\sum_{F\subseteq E(G)}(-1)^{|F|}x^{c(F)},
$$
where $c(F)$ counts components of the spanning <graph> $(V(G),F)$, including isolated vertices. Only $F=\varnothing$ gives $x^n$. A rank-one edge set is a single edge, giving coefficient $-m$ at $x^{n-1}$. Rank two comes from every two-edge subset, each with positive sign, and every triangle, each with negative sign. No other simple edge set has rank two: its nontrivial components must be a three-vertex component or two separate edges. Thus
$$
\boxed{a_0=1,\qquad a_1=m,\qquad a_2=\binom m2-t}.
$$
The displayed $a_2$ assertion concerns $n\ge3$; below this degree the corresponding coefficient is absent and its expression is zero.
Back to article page
