On the symmetric labelled structure of 2-regular graphs

Question

Let $G$ be the symmetric labelled structure of 2-regular graphs (indexed by the number of vertices) then $G(x)=\frac{e^{-\frac{x}{2}-\frac{x^2}{4}}}{\sqrt{1-x}}$. Could you help me to solve this problem, please?

Answer 1

You need to begin by finding the generating function for the number of connected $2$-regular graphs.

The connected $2$-regular graphs are the undirected cycle graphs. There are $(n-1)!$ labelled directed cycle graphs on $n$ vertices, so there are $\frac12(n-1)!$ labelled undirected cycle graphs on $n$ vertices: each undirected cycle graph can be directed in $2$ ways. Of course a cycle requires at least $3$ vertices, so if $c_n$ is the number of labelled undirected cycle graphs on $n$ vertices, we have $$c_n=\begin{cases} 0,&n=0,1,2\\\\ \frac12(n-1)!,&n\ge 3\;. \end{cases}$$

This yields the exponential generating function $$\begin{align*} C(x) &= \sum_{n\ge 0}c_n\frac{x^n}{n!}\\ &=\frac12\sum_{n\ge 3}\frac{(n-1)!}{n!}x^n\\ &=\frac12\sum_{n\ge 3}\frac{x^n}n\\ &=\frac12\left(\sum_{n\ge 1}\frac{x^n}n-x-\frac{x^2}2\right)\;. \end{align*}$$

You should recognize (or be able easily to discover) the generating function for the series $\sum_{n\ge 1}\frac{x^n}n$, and after that it’s just a matter of plugging it into the exponential formula to get $G(x)=e^{C(x)}$.