How many distinct subgraphs of a complete graph of $n$ labelled vertices are there such that the subgraph is a spanning tree connecting all the vertices and the degree of no vertex is more than $3$?
If $a_n$ denotes the number of such subgraphs, then for small values of $n$, by bruteforcing we have
- $a_1=1$,
- $a_2=1$,
- $a_3=3$,
- $a_4=16$,
- $a_5=120$.
How to find $a_n$ without bruteforcing?
The number of spanning trees in the complete graph $K_n$ with a degree $d_i$ specified for each vertex $i$ can be counted using Prüfer codes. The Prüfer code has $n-2$ slots, of which $d_i-1$ contain the label $i$, so the number of Prüfer codes corresponding to the specified degrees is the multinomial coefficient
$$ \binom{n-2}{d_1-1,\,d_2-1,\,\dots,\,d_n-1}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_{n}-1)!}\;. $$
We want all degrees to be $1$, $2$ or $3$. Denote the number of vertices with degree $k$ by $n_k$. Then we can choose groups of $n_1$, $n_2$ and $n_3$ vertices out of $n$, which yields another multinomial coefficient, and in the coefficient above the factorials are all $1$ or $2$ and yield a factor of $2^{n_3}$ in the denominator. Thus the number of trees is
$$ \binom n{n_1,n_2,n_3}\frac{(n-2)!}{2^{n_3}}\;. $$
Since we have $n$ vertices, we must have $n_1+n_2+n_3=n$, and since we have $n-1$ edges we must have $n_1+2n_2+3n_3=2n-2$. This allows us to express $n_1$ and $n_2$ in terms of $n_3$, namely $n_1=n_3+2$ and $n_2=n-2n_3-2$. Now we just have to sum over all possible values of $n_3$, i.e. the ones that make $n_2$ non-negative. The result is
$$ (n-2)!\sum_{n_3=0}^{\lfloor\frac n2\rfloor-1}2^{-n_3}\frac{n!}{n_3!(n_3+2)!(n-2n_3-2)!}\;. $$
This is OEIS sequence A003692. That page gives a recurrence relation:
$$ (n+2)a_n = n(2n-1)a_{n-1} + (n-3)(n-1)na_{n-2}\;. $$
(The indices are shifted with respect to the recurrence given at OEIS because the indexing of the OEIS sequence is off by $1$.)