Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / A / 1

For a nonnegative integer $q$, the chromatic polynomial $p_G(q)$ counts the proper vertex colourings of $G$ using a fixed set of $q$ colours. In a proper colouring, the endpoints of every edge have different colours. The counting function extends uniquely to a polynomial, as follows either from the recurrence below with the edgeless base case $p_G(x)=x^{|V(G)|}$ or from inclusion-exclusion.

Let $e=uv$. Every proper colouring of $G-e$ falls into exactly one of two classes. If $u$ and $v$ have different colours, it is a proper colouring of $G$. If they have the same colour, identifying $u$ and $v$ gives a proper colouring of the contracted graph $G/e$, and this correspondence is bijective. Parallel edges produced by contraction impose identical conditions and can be suppressed. Hence, at every nonnegative integer $q$,Since polynomials agreeing at infinitely many values agree identically, the deletion-contraction recurrence for the chromatic polynomial isThroughout, the graphs are finite and simple, as in the usual convention for these statements.

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.

An inclusion-exclusion proof gives the coefficients directly. For an edge set $F\subseteq E(G)$, let $c(F)$ be the number of connected components of the spanning graph $(V(G),F)$, including isolated vertices. Requiring the two endpoints of every edge of $F$ to have the same colour leaves exactly $x^{c(F)}$ colourings. Thus the chromatic polynomial inclusion-exclusion formula isConsider a term with $n-c(F)=i\le k-2$. If $(V(G),F)$ contained a cycle, that cycle would have length at least $k$. The component containing it would have at least $k$ vertices and hence contribute at least $k-1$ to $n-c(F)$, a contradiction. Therefore $F$ is a forest. For a forest, $n-c(F)=|F|$, so necessarily $|F|=i$.

Conversely, every $i$-element edge set with $i\le k-2$ is a forest, since a cycle would require at least $k$ edges. Thus exactly $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ edge sets contribute to the coefficient of $x^{n-i}$, and they all have sign $(-1{)}^i$. ConsequentlyThis proves girth determines initial chromatic coefficients without requiring the suggested double induction.