A graph G is defined by a set V(G) of vertices, a set E(G) of edges, and a relation of incidence which associates with each edge two distinct vertices called its ends. We consider only the case in which V(G) and E(G) are both finite.

An n-colouring of G is usually defined as a mapping f of V(G) into the set of integers { 1, 2,…, n} which maps the two ends of any edge onto distinct integers. The integers 1 to n are the n "colours". Much work has been done on n-colourings in recent years, especially by G. A. Dirac.