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

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.