Colouring

A (vertex) colouring is an assignment of colours from some
set C to the vertices of a graph G, that is a map from VG -> C.
An edge colouring is similarly a map from EG -> C.

We concentrate on proper colourings, for which adjacent
vertices (edges) have different colours.

The number of different ways of vertex colouring a graph G with n
different colours is a polynomial function of n: the chromatic
polynomial of G. We can compute this function, and show that
it is a polynomial by the cut-fuseprocess.

Select an edge e = xy of G and let G\e and G/e be the results of deleting
(cutting) and contracting (fusing) the edge e respectively. We note
that every proper colouring of G\e either has the same colour on x and y,
in which case it induces a proper colouring of G/e, or else it has
different colours on x and y in which case it is a proper colouring
of G. So P_G = P_G\e - P_G/e.
Induction on the number of vertices and then the number of edges
completes the proof, as a graph with k vertices and no edges has
P(n) = n^k.