Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / A / 1 / b / 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 giveswith $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}\ge 0$. Moreover $a_0=b_0=1$ andFor a graph with at least one vertex, $p_G(0)=0$, so the constant term vanishes. ThereforeIn 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.