Counting techniques to find all nonisomorphic graphs with six vertices, all having degree $2.$

Question

First of all, the graphs considered are undirected & parallel edges and loops are allowed.

My attempt : By handshaking lemma, $$\text{Sum of degrees of all vertices} = 2 (\text{Number of edges})$$

Thus we get $\frac {2+2+2+2+2+2}{2}=\text{Number of edges}=6.$

Therefore we have to find all nonisomorphic graphs with six vertices and six edges.

Then I formed six cases based on number of cycles in such nonisomorphic graphs. Each case was then divided into subcases where we count graphs with number of loops and parallel edges in it.

My question is whether there exist other counting techniques in such scenario?

Answer 1

Each one of those isomorphism classes can be represented as an integer partition of 6, that is, a way of writing positive numbers which add up to 6, where the order doesn't matter. For example your 3(i), 3(ii) and 3(iii) correspond to $2 + 2 + 2, 4 + 1 + 1$ and $3 + 2 + 1$ respectively. There is a well-understood theory of integer partitions which would allow you to, for example, compute the number of partitions of some large integer $n$ without having to explicitly write them out, and therefore to compute the number of nonisomorphic graphs with $n$ vertices all having degree 2. (In the $n = 6$ case that theory is probably overkill.)

Answer 2

An alternative approach is given by Riddell's formula, which transforms the generating function for the number of connected graphs of $n$ vertices with property $P$ into the generating function for the number of graphs of $n$ vertices whose connected components have property $P$.

Here you appear to be working with unlabelled graphs, so the number of connected graphs of $n$ vertices with the property that each vertex has degree $2$ is $1$ (for $n \ge 1$ given your convention on loops), and we work with ordinary generating functions. We have¹ g.f. $A(x) = x + x^2 + x^3 + \ldots = \frac{x}{1-x}$ for connected graphs. Then we get g.f. for all graphs of $\exp\left(\sum_{k=1}^\infty \frac{A(x^k)}{k} \right) = \exp\left(\sum_{k=1}^\infty \frac{x^k}{k(1-x^k)} \right)$.

This is even more overkill as an approach than going directly to the partition function, although it winds up in the same place, as witness the mention of the above generating function in OEIS A000041.

---

¹ I'm brushing under the carpet some technicalities around graphs with $0$ vertices.