= Solution
{c}
For a finite <graph> $G$, its <chromatic polynomial> $p_G(x)$ is the <polynomial> whose value at each positive <integer> $q$ counts <proper vertex colourings> of $G$ from a fixed palette of $q$ labelled colours. Adjacent <vertices> must receive different colours, and unused colours are allowed.
For an <edge> $e=uv$, the <deletion-contraction recurrence for the chromatic polynomial> is
$$
\boxed{p_G(x)=p_{G-e}(x)-p_{G/e}(x).}
$$
Here $G-e$ deletes only the <edge> $e$, while $G/e$ performs <edge contraction>, identifying $u,v$ and removing $e$. Any parallel <edges> produced by <edge contraction> can be replaced by a single <edge>, since their constraints on <proper vertex colourings> are identical.
Indeed, the <proper vertex colourings> of $G-e$ in which $u,v$ differ are precisely those of $G$, while those in which $u,v$ agree correspond bijectively to <proper vertex colourings> of $G/e$. This proves the equality for every positive <integer> $q$, hence as a <polynomial identity>. Together with $p_G(x)=x^{|V(G)|}$ for a <graph> without <edges>, the recurrence also proves by <mathematical induction> that the counting function is a <polynomial>.
Back to article page
