= Solution
For a positive integer $t$, the <chromatic polynomial> $P_G(t)$ is defined to be the number of proper <graph colourings>[vertex colourings] of $G$ using a fixed palette of $t$ colours.
We prove that this counting function is a polynomial by induction on the number of <edges>. If $G$ has $n$ vertices and no edges, every assignment of colours is proper, so
$$
P_G(t)=t^n.
$$
Otherwise choose an edge $e=uv$. Every proper colouring of $G-e$ either gives $u,v$ different colours, in which case it is a colouring of $G$, or gives them the same colour, in which case it corresponds to a proper colouring of the contracted graph $G/e$. Hence the <deletion-contraction recurrence for the chromatic polynomial> is
$$
P_G(t)=P_{G-e}(t)-P_{G/e}(t).
$$
Both terms on the right are polynomials by induction, so $P_G$ is a polynomial.
Back to article page
