Let $f(n)$ be the number of simple undricted graphs with $n$ vertices numbered ${1,2,\dots,n}$ s.t every vertex degree is 2.
Find a recurrence relations for $f(n)$
My attempt:
Since that the degree of every vertex is $2$, the number of vertices is at least $3$. Now there are two possible options for the $n^{th}$ vertex location:
- In a circle of 4 or more vertices.
- In a circle of excatly 3 vertices.
The first option is quite easy - $(n-1)f(n-1)$. In the second option, I need to choose the other 2 vertices $\binom{n-1}{2}$. Now I'd like to multiply it by $f(n-3)$ but I don't think I can, since $f(n)$ is defined by the vertices numbered ${1,2,\dots,n}$. And if, for intance, the vertices numbered 1 and 3 are in a circle with the $n^{th}$ one, it's not $f(n-3)$.
( Note that joriki's answer is more to the point, and leads to the simpler recursion $$f(n)=(n-1)f(n-1)+{n-1\choose2}f(n-3)\ .\quad)$$ The graphs $\Gamma$ in question are disjoint unions of cycles $\Gamma_i$ of length $r_i\geq3$.
For the induction you cannot just throw in the vertex $v_n$ into an existing cycle. Instead you have to build the full cycle containing $v_n$.
One has $f(0)=1$, $\>f(1)=f(2)=0$, $\>f(3)=1$.
For $n\geq4$ we argue as follows: Vertex $v_n$ is in a cycle of length $r\in[3..n]$. This cycle can be chosen in $$(n-1)(n-2)\cdots\bigl(n-(r-1)\bigr)/2$$ ways, whereby the $/2$ accounts for the the idea that the graphs $\Gamma_i$ should be nondirected. After the cycle containing $v_n$ has been chosen there are $n-r$ vertices left which then can be arranged in $f(n-r)$ ways to undirected cycles. Summing it up we obtain the recursion $$f(n)=\sum_{r=3}^n {(n-1)(n-2)\cdots(n-r+1)\over2} f(n-r)\qquad(n\geq4)\ .$$ One obtains $$\bigl(f(n)\bigr)_{n\geq0}=(1, 0, 0, 1, 3, 12, 70, 465, 3507, 30016, 286884,\ldots)\ .$$ This is sequence A001205 at OEIS.