Deletion-contraction recurrence for the chromatic polynomial
= Deletion-contraction recurrence for the chromatic polynomial
For a non-loop edge $e$,
$$
P_G(t)=P_{G-e}(t)-P_{G/e}(t).
$$
The first term counts colourings after deleting $e$; the second subtracts those giving its endpoints the same colour, which correspond to colourings of the contraction. Together with $P_G(t)=t^{|V(G)|}$ for an edgeless graph, induction proves that $P_G$ is a polynomial.