Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 2 / b

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. ThusFor an edgeless graph on $n\ge 1$ 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 giveswith absent coefficients interpreted as zero. Each coefficient remains nonnegative. Both terms have zero constant coefficient for nonempty graphs, so the resulting expansion isThis induction simultaneously proves the counting function is a polynomial.