Chromatic Polynomial

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