 Deletion-contraction recurrence for the chromatic polynomial

For a non-loop edge $e$,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.