Generating function for number of graphs with all vertices of degree 1 or 2

combinatoricsgenerating-functionsgraph theory

To elaborate on the title, I am trying to find the exponential generating function for $\{a_n\}_{n \geqslant 0}$, where $a_n$ is the number of graphs on $n$ vertices with an odd number of connected components, where every vertex is of degree 1 or 2.

My attempt thus far is as follows (also, I am using the card system discussed in chapter 3 here: https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf)

Let cards correspond to connected graphs with all vertices of degree 1 or 2.

Then hands correspond to forests of such graphs, so a hand with an even number of cards whose weights sum to $n$ is counted by $a_n$.

We can count all such graphs using the function $e_T(D(x))$, where $T = \{2z+1 | z \in \mathbb{Z_+}\}$ and $D(x) = \sum_{n\geqslant0}d_nx^n/n!$.

This follows because $e_T(D(x))$ as described in the book, is the generating function for the sequence $h_n(T)$, where $h_n(T)$ is the number of hands of weight $n$ with a number of cards which is in $T$.

I know this is probably introducing a lot of notation, but what I am having a problem with is that I don't know what $d_n$ is, and it seems like there is not an easy way to compute it. So I am thinking that either there must be some other way to construct my cards and hands, or I am missing an obvious way of computing $d_n$. So in some respect the advice I need may not require you to understand all the notation.

Thanks in advance for any help, I really appreciate it!

And another thing I should mention is, in general, $e_T(x) = \sum_{n\in T}x^n/n!$, so I believe in my case $e_T(x) = \frac{(e^x-e^{-x})}{2} – 1$. It would be helpful if someone could verify that I am correct about that as well.

If it would be helpful for me to elaborate anywhere, please let me know!

Best Answer

$D(x)$ is supposed to be the exponential generating function for the number of connected graphs on $n$ labelled vertices with maximum degree $2$.

There are two types of graphs like this: paths and cycles.

  • There are $\frac{n!}{2}$ paths, provided $n \ge 2$. We can label the vertices on a path in $n!$ ways, but reversing the order produces the same path.
  • There are $\frac{(n-1)!}{2}$ cycles, provided $n \ge 3$. Deleting vertex $n$ produces a path on $(n-1)!$ vertices, and we can just count those.

So we get \begin{align} D(x) &= \sum_{n \ge 2}\frac{n!}{2} \cdot \frac{x^n}{n!} + \sum_{n \ge 3} \frac{(n-1)!}{2} \cdot \frac{x^n}{n!} \\&= \frac12\left(\frac{1}{1-x} - 1 - x\right) + \frac12\left(-\log(1-x) - x - \frac{x^2}{2}\right). \end{align} To get the number of graphs of this form with an odd number of connected components, we take $$ \frac{e^{D(x)} - e^{-D(x)}}{2}. $$ I see no reason to subtract $1$.

Related Question