Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / A / 2 / c / 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: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 expressionwhere $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. ThusThe displayed $a_2$ assertion concerns $n\ge 3$; below this degree the corresponding coefficient is absent and its expression is zero.