7
$\begingroup$

(This is a question I already more or less know how to answer, but I thought I'd pose it as a puzzle for others who might enjoy solving it, and post my own answer after a day or so. It came from misreading this question.)

Consider the collection of finite, simple, undirected graphs $G$ such that every vertex of $G$ has degree at most $2$.

  1. How many labeled such graphs on $n$ vertices are there?
  2. How many unlabeled such graphs on $n$ vertices are there?

Answers in the form of generating functions, asymptotics, etc. are fine; the goal is just to say as much as possible. Have fun!

$\endgroup$
2
$\begingroup$

For the sake of brevity I won't include complete proofs. It's not hard to show by strong induction that a graph has all vertices of degree $\le 2$ iff it's a disjoint union of path graphs $P_k, k \ge 1$ and cycle graphs $C_k, k \ge 3$, including the path graph $P_1$ of length $0$ consisting of a single isolated vertex.

Write $a_n$ for the number of labeled such graphs on $n$ vertices. The exponential formula gives an exponential generating function

$$\begin{align} A(z) = \sum_{n \ge 0} \frac{a_n}{n!} z^n &= \exp \left( \sum_{k \ge 3} \frac{z^k}{2k} + z + \sum_{k \ge 2} \frac{z^k}{2} \right) \\ &= \exp \left( \frac{1}{2} \left( \log \frac{1}{1-z} - z - \frac{z^2}{2} + 2z + \frac{z^2}{1 - z} \right) \right) \\ &= \frac{\exp \left( \frac{z}{2 - 2z} - \frac{z^2}{4} \right)}{\sqrt{1 - z}} \end{align}$$

where the term $\sum_{k \ge 3} \frac{z^k}{2k}$ counts the contribution of the cycle graphs and the term $z + \sum_{k \ge 1} \frac{z^k}{2}$ counts the contribution of the path graphs; we get these expressions by counting the number of labeled such graphs and then dividing by $n!$. By the orbit-stabilizer theorem this is equivalent to computing $z^n$ divided by the order of the automorphism group of a cycle graph (a dihedral group $D_k$) or path graph (trivial for $k = 1$ and $C_2$ otherwise) respectively.

Plugging into WolframAlpha gives the first few terms $1, 1, 2, 8, 41, 253 \dots$ and plugging these into the OEIS gives that this sequence is A136281, which calls these graphs "thunderstorm graphs."

The generating function has an essential singularity at $z = 1$ which suggests saddle point asymptotics, as described e.g. in Chapter VIII of Flajolet and Sedgewick's Analytic Combinatorics. The simplest saddle point bound gives

$$\frac{a_n}{n!} \le \frac{A(r)}{r^n}, r > 0$$

and finding $r$ optimizing this bound exactly is a pain but if we optimize it approximately the dominant term comes from the $\exp \left( \frac{z}{2-2z} \right)$ factor and gives $r \approx 1 - \frac{1}{\sqrt{2n}}$, which after some approximations gives

$$\frac{a_n}{n!} \lesssim \exp \left( \sqrt{2n} \right)$$

up to polynomial factors in $n$, which gives via Stirling's formula

$$\boxed{ a_n \lesssim \exp \left( n \log n - n + \sqrt{2n} \right) }$$

again up to polynomial factors in $n$. According to the OEIS this is actually the right asymptotic up to a multiplicative constant of $\frac{1}{\sqrt{2e}}$ which can probably be proven by applying the saddle point method more carefully.


Now write $b_n$ for the number of unlabeled such graphs on $n$ vertices. Up to isomorphism such a graph is determined by a count of how many components it has isomorphic to a given path or cycle graph, which gives the ordinary generating function

$$\begin{align} B(z) = \sum_{n \ge 0} b_n z^n &= \frac{1}{\left( \prod_{n \ge 3} (1 - z^n) \right) \left( \prod_{n \ge 1} (1 - z^n) \right)} \\ &= (1 - z)(1 - z^2) P(z)^2 \end{align}$$

where $P(z) = \frac{1}{\prod_{n \ge 1} (1 - z^n)}$ is the generating function of the partition function $p(n)$. Plugging into WolframAlpha gives the first few terms $1, 1, 2, 4, 7, 11, 19, 29, \dots$ and plugging these into the OEIS gives A003292.

The generating function factorization above allows us to write $b_n$ in terms of the partition function as follows. If we define

$$q_n = \sum_{k=0}^n p(k) p(n-k)$$

to be the coefficients of the square $P(z)$ of the generating function of the partition numbers, then

$$b_n = q_n - q_{n-1} - q_{n-2} + q_{n+3}.$$

So the asymptotics of $b_n$ are closely related to the asymptotics of the partition function. In fact we can use saddle point asymptotics again here, similar to the saddle point asymptotics for the partition function itself (see this blog post) using the approximation

$$\log P(z) \approx \frac{\pi^2}{6(1 - z)}$$

which gives an approximate saddle point $r = 1 - \frac{\pi}{\sqrt{3n}}$ for the saddle point bound $b_n \le \frac{B(r)}{r^n}$, which after some simplifications and approximations gives

$$\boxed{ b_n \lesssim \exp \left( \pi \sqrt{ \frac{4n}{3} } \right) }$$

again up to polynomial factors in $n$ (compare to the well-known asymptotic $p(n) \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.