[ Acknowledgement: all the tedious algebraic expansions in this article were performed by wolframalpha. ]

## Counting Graphs

One of the most surprising applications of Burnside’s lemma and Polya enumeration theorem is in counting the number of graphs up to isomorphism.

Problem. Find the number of simple graphs with n vertices, up to isomorphism.

Let *V* be a set of *n* vertices, and *E* be the set of all 2-element subsets of *V*. E.g. for *n*=5:

*V*= {*a*,*b*,*c*,*d*,*e*};

*E*= {{*a*,*b*}, {*a*,*c*}, {*a*,*d*}, {*a*,*e*}, {*b*,*c*}, {*b*,*d*}, {*b*,*e*}, {*c*,*d*}, {*c*,*e*}, {*d*,*e*}}.

The full symmetric group then acts on *E*. Each graph corresponds to a colouring of *E* by *Y* = {black, white} and two graphs are isomorphic if and only if they’re isotopic under *G* – i.e. belong to the same orbit under *G*. Our objective is to compute the number of unique colourings by applying Polya enumeration theorem.

Clearly, *c*(*g*) – the number of orbits of *g* acting on *E* – only depends on the equivalence class of *g* in *G*; in particular for *n*=5, the number of cases is reduced from 5!=120 to 7.

*g*=*e*:*c*(*g*) =*C*(5, 2) = 10;

**[10×]***g*=(*a*,*b*): edges*ac*and*bc*must share the same colour, as do {*ad*,*bd*}, {*ae*,*be*}, so*c*(*g*) = 7;**[20×]***g*=(*a*,*b*,*c*): edges*ad*,*bd*and*cd*must have the same colour, as do {*ae*,*be*,*ce*} and {*ab*,*bc*,*ac*}, so*c*(*g*) = 4;**[30×]***g*=(*a*,*b*,*c*,*d*): edges*ae*,*be*,*ce*and*de*have the same colour, as do {*ab*,*bc*,*cd*,*da*} and {*ac*,*bd*}, so*c*(*g*) = 3;**[24×]***g*=(*a*,*b*,*c*,*d*,*e*): we get two orbits {*ab*,*bc*,*cd*,*de*,*ae*} and {*ac*,*bd*,*ce*,*ad*,*be*} so*c*(*g*)=2;**[15×]***g*=(*a*,*b*)(*c*,*d*): we get {*ae*,*be*}, {*ce*,*de*}, {*ac*,*bd*}, {*ad*,*bc*}, {*ab*}, {*cd*} so*c*(*g*)=6;**[20×]***g*=(*a*,*b*)(*c*,*d*,*e*): we get {*ab*}, {*cd*,*de*,*ce*} and all the remaining edges form a single orbit so*c*(*g*)=3.

Hence the number of graphs with 5 vertices, up to isomorphism, is:

The following diagram lists all isomorphism classes of simple graphs with 5 vertices and up to 5 edges.

## Counting Graphs II

In fact, with just a bit more effort, we can compute the number of graphs with 5 vertices and *e* edges, for each 0 ≤ *e* ≤ 10. Recall that each graph (ignoring symmetry) is simply a map *E* → {black, white}. Let *X* be the set of all such graphs; the group acts on *X* by permuting the edges around.

Now, we assign a weight to each colour: black→1 and white→0. Each graph *E* → {black, white} then gets a weight which is its number of edges. Let *X _{i}* be the set of elements in

*X*with weight

*i*; it’s easy to see that .

Our objective is to compute , the number of isomorphic classes of simple graphs with 5 vertices and

iedges.

To that end, define the polynomial . Burnside’s lemma gives:

Thus, we need to evaluate the power series for each *g*.

*g*=*e*: since , this is just .

*g*=(*a*,*b*) : as worked out earlier, the non-trivial orbits are {*ac*,*bc*}, {*ad*,*bd*} and {*ae*,*be*}. For each of these three orbits, the weight is either 0 or 2, so we get a factor of . For the remaining 4 singleton orbits, we get a factor of , so the summand is .*g*=(*a*,*b*,*c*): the orbits are {*de*}, {*ad*,*bd*,*cd*}, {*ae*,*be*,*ce*} and {*ab*,*bc*,*ac*}. Each of the three 3-element sets contributes a factor of while the singleton set contributes (1+*t*), hence the summand is .

Eventually, we get all the seven power series.

which gives . Thus, there are 1 graph with 1 edge, 2 graphs with 2 edges, 4 graphs with 3 edges, … up to isomorphism.

## Polya Enumeration Theorem Revisited

Inspired by the above example, we define:

Definition. Let G be a finite group acting on finite set X of size k. Then thecycle indexis the polynomial:where is the number of cycles (or orbits) in g of length c.

**Examples**.

- Consider
*S*_{3}acting on {1, 2, 3}. Then each term gives:*g*=*e*: ;**[3×]***g*=(*a*,*b*): ;**[2×]***g*=(*a*,*b*,*c*): , so we have .

- Consider acting on the set of edges
*E*earlier. We have:

Now we’re ready to describe a more general form of Polya enumeration theorem. As before, *G* acts on set *X*, and we consider the set of all colourings *X**→Y*. But now each colour is endowed with a *weight*. If we let be the set of colourings with weight *i*, then our objective is to compute via the power series

As worked out before, to do that we need to compute:

, for each *g* in *G*.

Now if we write *g* as a product of cycles: *g* = (cycle 1)(cycle 2) … , where there are cycles of length *c*, then *each cycle must be of uniform colour*! In other words, each cycle contributes a term of where is the number of colours of weight *w*. Hence:

Writing , this gives: . Summing up:

Let’s summarise all we’ve learnt.

Polya Enumeration Theorem B. Suppose we have colours of weight w and . Then the number of colourings with a specified weight is given by the generating function:.

E.g. in our earlier example of graph counting, we have *f*(*x*) = 1+*x* so the resulting generating function is as we saw above.

## Example 1

On a 2*k* × 2*k* chessboard, each square is to be coloured black or white. Two colourings are identical if they can be obtained from each other by rotation or reflection. Find the generating function for the number of colourings with a specified number of black squares.

**Solution**

Let’s consider the symmetries of a square.

In the first case, we get *k*^{2} cycles of length 4 each. In the second and third cases, we get 2*k*^{2} cycles of length 2 each. In the final case, we get 2*k* cycles of length 1 and *k*(2*k*-1) cycles of length 2. Hence:

The final answer is thus:

Here are some small examples.

*k*=1: ;*k*=2:

More generally, we can consider colours with *vectorial weights*. For example, if each colour has weight (*v*, *w*), then we write:

where denotes the number of colours of weight (*v*, *w*). Then Polya’s enumeration theorem can be further generalised: the number of colourings with a specified vectorial weight (*v*, *w*) is given by the coefficient of in:

## Example 2

Find the number of ways to colour the 12 edges of a cube with {red, green blue} such that each colour occurs on an even number of edges. Two colourings are considered identical if they’re obtained from each other via a rotation.

**Solution**

Label the 12 edges of a cube as follows, together with three axes of rotation.

Let’s compute the orbits of the various rotations. There should be 24 rotations in all.

- Identity: 12 singleton orbits, {1}, {2}, …, {12}.
**[6×]**Rotation about axis 1 (90 deg): {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}.**[3×]**Rotation about axis 1 (180 deg): {1, 3}, {2, 4}, {5, 7}, {6, 8}, {9, 11}, {10, 12}.**[6×]**Rotation about axis 2: {5}, {7}, and 5 orbits of size 2.**[8×]**Rotation about axis 3: 4 orbits of size 3.

Hence the cycle index is:

[ Note: without tracing the exact orbits, we can conclude that the rotation about axis 2 has exactly five orbits of size two. Indeed, since the rotation has order 2, each cycle size is either 1 or 2. The only fixed edges are 5 and 7 so the remaining edges must be paired into five orbits of size two each. ]

We need to compute the number of colourings where green and blue each occurs an even number of times, so assign weight to each colour: red=(0, 0), green=(1, 0) and blue=(0, 1). The weight polynomial is *f*(*x*, *y*) = 1+*x*+*y* so the resulting generating function is:

To sum up the coefficients of where *i* and *j* are both even, compute the sum

. ♦

## The Case of Full Symmetric Group

Suppose |*X*|=*k* and |*Y*|=*n* and *G* is the full symmetric group . In the previous article, considering this group led us to the formulation of Stirling numbers. Let’s consider the case of the cycle index:

What can we say about this power series?

To answer them, let’s assign some weights to the *n* colours. To distinguish all the *n* distinct colours, we’ll assign an (*n*-component) vectorial weight:

colour 1 ↔ (1, 0, …, 0), colour 2 ↔ (0, 1, …, 0), … …, colour *n* ↔ (0, 0, …, 1).

Hence, the weight of a colouring tells us the number of occurrences of each colour. The corresponding weight polynomial is then a linear function in *n* variables:

Applying the multivariate version of the Polya enumeration theorem, we see that the number of colourings of a specified weight is given by the generating function:

where is the *i*-th power symmetric function. The question is: how many colourings are of weight , up to symmetry? Since we have the full symmetric group acting on *X*, the answer is obvious: 1 if and 0 otherwise. Now if we multiply this by an auxiliary and sum over all *k*=|*X*|, we get the resulting power series:

Writing each term

we get the final result:

**Example**

To compute the cycle index for , let . We need to compute the expansion of exp(*T*) until *T*^{5} and find the coefficient of *t*^{5}.

- ;
- ;
- ;
- ;
- .

Hence, the final sum is

In conclusion, in the group , there are:

- 1 identity element,
- 24 elements of type (
*a*,*b*,*c*,*d*,*e*), - 30 elements of type (
*a*,*b*,*c*,*d*), - 20 elements of type (
*a*,*b*)(*c*,*d*,*e*), - 20 elements of type (
*a*,*b*,*c*), - 15 elements of type (
*a*,*b*)(*c*,*d*), and

- 10 elements of type (
*a*,*b*).

All these were obtained via generating functions.