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

For a positive integer $x$, $p_G(x)$ counts proper vertex colorings using a labelled palette of $x$ colors. Choose an edge $e=uv$. Proper colorings of $G-e$ divide into those in which $u,v$ have different colors, counted by $p_G(x)$, and those in which they have the same color, counted by $p_{G/e}(x)$. Thuswhere parallel edges after contraction are suppressed. Induction, using $p_G(x)=x^{|V(G)|}$ for an edgeless graph, produces a polynomial agreeing with every integer coloring count. The polynomial is unique because two polynomials agreeing at infinitely many integers are identical.