Number of non-isomorphic simple graphs whose degrees of all vertices is less than or equal to $2$

combinatoricsdiscrete mathematicsgraph theory

I an looking at the number of non-isomorphic simple graphs $(V,E)$ such that $|V|=n$ and $\forall v \in V, d(v)\le 2$

Specifically, I am asked to find this number for $n =8$ and $n = 9$. But wonder if there is a nice recursive formula.

Attempt:
I let $d_n$ denote this number. By trying out a few examples, I see $d_1=1, d_2=2, d_3=4, d_4=7, d_5=11$. My graphs are essentially made up of cycles, chains (sticks) and isolated points. I also tried looking at consecutive $n$'s but to no success.

Best Answer

This is A003292 in the OEIS. There is no simple recurrence, but there is a nice generating function: $$\frac1{1-x}\frac1{1-x^2}\prod_{k=3}^\infty\frac1{(1-x^k)^2}$$ This generating function arises simply: in graphs with maximum degree $2$, each connected component is a single vertex, a single edge (two vertices), a cycle on $n\ge3$ vertices or a path on $n\ge3$ vertices. These explain the $\frac1{1-x},\frac1{1-x^2}$ and remaining factors of the generating function respectively.

We have $d_8=46$ and $d_9=70$.