In this chapter and the next one we shall investigate expansions of the chromatic polynomial which involve relatively few subgraphs in comparison with the expansion of Chapter 10. The idea first appeared in the work of Whitney (1932b), and it was developed independently by Tutte (1967) and researchers in theoretical physics who described the method as a ‘linked-cluster expansion’ (Baker 1971). The simple version given here is based on a paper by the present author (Biggs 1973a). There are other approaches which use more algebraic machinery; see Biggs (1978) and lle.

We begin with some definitions. Recall that if a connected graph Г is separable then it has a certain number of cut-vertices, and the removal of any cut-vertex disconnects the graph. A non-separable subgraph of Г which is non-empty and maximal (considered as a subset of the edges) is known as a block. Every edge is in just one block, and we may think of Г as a set of blocks ‘stuck together’ at the cut-vertices. In the case of a disconnected graph we define the blocks to be the blocks of the components. It is worth remarking that this means that isolated vertices are disregarded, since every block must have at least one edge.

Let Y be a real-valued function defined for all graphs, and having the following two properties.

P1: Y(Г) = 1 if Г has no edges;

P2: Y(Г) is the product of the numbers Y(B) taken over all blocks B of Г.