Number of spanning trees in a wheel graph without an external edge.

Question

How many different spanning tree contains n-element graph shown above? Determine the generating function for considered sequence. I am asking for advice.

Answer 1

Consider a tree of that form with final vertex $n+1$, there are two cases. Case $1$ is when vertex $(n+1)$ is connected to vertex $0$. In this case we classify all the trees according to how many vertices are in the same external block as vertex $n+1$ (an external block is a path between consecutive external vertices. Notice that if we delete all of the vertices in an external block we'll get a tree with $n+1-k$ external vertices where $k$ is the number of vertices in the block.

Hence the number of trees of this type is $\sum\limits_{k=1}^{n+1}f_{n+1-k}$

Now count the vertices in which vertex $n+1$ is not connected to vertex zero. Then after removing that vertex we get a tree in which the maximum vertex is $n$. There are $f_n$ of this type.

Then the recursion is $f_{n+1}=f_n+\sum\limits_{i=0}^nf_i$

You also have $f_{0}=1,f_{1}=1,f_{2}=3$

From here you can follow: $f_{3}=8,f_{4}=21,f_{5}=55$