Let be a Graph. The chromatic polynomial is where is the number of -colourings of Proposition Let be the Contraction along edge of Then Proof Every colouring of where are coloured differently corresponds uniquely to a colouring of Every colouring of where are coloured the same corresponds uniquely to a colouring of . Corollary is a polynomial of degree Proposition Let be a graph with vertices and edges. Then