# Find a generating function for unlabeled graphs

Let's take a graph(undirected) of $$m$$ edges and $$3$$ vertices. Now I want to derive a polynomial for which the coefficient of $$x^m$$ denotes the number of unlabeled graphs of $$m$$ edges.

How to derive the polynomial in this case? Also is deriving a polynomial means deriving a generating sequence?

Here we require the cycle index of the action on the edges of the symmetric group $$S_3$$ on the vertices. We find:

• The identity: $$a_1^3.$$
• Three reflections: $$3 a_1 a_2.$$
• Two rotations: $$2 a_3.$$

We get for the cycle index

$$Z(G_3) = \frac{1}{6} ( a_1^3 + 3 a_1 a_2 + 2 a_3 ).$$

Evaluate at $$1+z$$ for the generating function:

$$Z(G_3; 1+z) = \frac{1}{6} ((1+z)^3 + 3 (1+z) (1+z^2) + 2 (1+ z^3)) \\ = \frac{1}{6} (1+3z+3z^2+z^3 + 3+3z^2+ 3z + 3z^3 + 2+2z^3) = 1 + z + z^2 + z^3.$$

This means there is one graph on three vertices taking into account ismorphisms having zero, one, two and three edges.

The general case is described and implemented at the following MSE link.