K4 has 16 spanning trees. I believe there are two non-isomorphic spanning trees in K4. Is this because half of the spanning trees have the sequence (1,2,2,1) as the degrees of their vertices, while the other half have (1,3,3,1)? Or is there some other reason why just two of the spanning tree graphs of K4 are non-isomorphic?
[Math] The number of non-isomorphic spanning trees in K4
graph theory
Related Solutions
Let the vertices along the top of $L_{n+1}$ be $u_1,\dots,u_{n+1}$ and those along the bottom be $v_1,\dots,v_{n+1}$. There’s a bijection between spanning trees of $L_{n+1}$ that contain the edges $\{u_n,u_{n+1}\}$, $\{u_{n+1},v_{n+1}\}$, and $\{v_n,v_{n+1}\}$ and spanning trees of $L_n$ that contain the edge $\{u_n,v_n\}$. Let $s_n$ be the number of spanning trees of $L_n$ that include $\{u_n,v_n\}$. Then $t_{n+1} = 3t_n + s_n$, and $s_{n+1} =$ ?
Added: I now see how to get a recurrence for the $t_n$ directly, without using an auxiliary sequence. Start with any spanning tree of $L_n$. As you said, you can always add one of the three figures in your second picture to it to get a spanning tree of $L_{n+1}$, and that accounts for $3t_n$ spanning trees. You can add your last picture to it if and only if it contains $\{u_n,v_n\}$, in which case you must erase $\{u_n,v_n\}$; that accounts for another $t_n-k$ spanning trees, where $k$ is the number of spanning trees of $L_n$ that don’t contain $\{u_n,v_n\}$. So when does a spanning tree $T$ of $L_n$ not contain $\{u_n,v_n\}$? Exactly when $T$ does contain both $\{u_{n-1},u_n\}$ and $\{v_{n-1},v_n\}$, which is exactly when the part of $T$ in $L_{n-1}$ is a spanning tree of $L_{n-1}$. In other words, there are $t_{n-1}$ spanning trees of $L_n$ that include the edge $\{u_n,v_n\}$: $k=t_{n-1}$, and $L_{n+1}$ has $t_n-t_{n-1}$ spanning trees that include your last picture. This makes a grand total of $$t_{n+1}=3t_n+(t_n-t_{n-1})=4t_n-t_{n-1}$$ spanning trees of $L_{n+1}$.
But I found the analysis much easier with the auxiliary sequence. As long as your recurrences are linear, it’s not too hard to combine them by very elementary means. For instance, suppose that you have this system: $$\begin{cases} t_{n+1}=at_n+bs_n\tag{1}\\ s_{n+1}=ct_n+ds_n \end{cases}$$
Then $$\begin{cases} dt_{n+1}=adt_n+bds_n\\ bs_{n+1}=bct_n+bds_n, \end{cases}$$
so $dt_{n+1}-bs_{n+1}=(ad-bc)t_n$. As long as $ad-bc\ne 0$, you can solve this for $s_{n+1}$ to get $$s_{n+1}=\frac{d}{b}t_{n+1}-\frac{ad-bc}{b}t_n,$$ or, equivalently, $$s_n=\frac{d}{b}t_n-\frac{ad-bc}{b}t_{n-1}.$$ Substitute this into the first equation of $(1)$ to get $$t_{n+1}=(a+d)t_n+(ad-bc)t_{n-1}.$$
As you said, there will be five edges, and each $A$-point will be incident to least one edge. There are $2$ partitions of $5$ into $3$ nonempty parts, namely $(3,1,1)$ and $(2,2,1)$.
As for $(3,1,1)$, you can choose the $A$-vertex of degree $3$ in three ways, and you can connect each of the other two $A$-vertices to a $B$-vertex at libitum in $9$ ways. Each of these $27$ times you will get a spanning tree of $K_{3,3}$.
Concerning $(2,2,1)$ you can choose the $A$-vertex of degree $1$ in $3$ ways and connect it with the $B$-vertex of your choice in $3$ ways. Then you can connect the first $A$-vertex of degree $2$ with two $B$-vertices of your choice in $3$ ways and connect the second $A$-vertex of degree $2$ with two $B$-vertices of your choice, but not the same two as before, in $2$ ways, giving a total of $54$ possibilities, and each of these leads to a spanning tree of $K_{3,3}$.
Therefore the overall total is $81$.
Best Answer
You're essentially asking for the number of non-isomorphic trees on $4$ vertices. Here they are:
We can verify that we have not omitted any non-isomorphic trees as follows.
The total number of labelled trees on $n$ vertices is $n^{n-2}$, called Cayley's Formula. When $n=4$, there are $4^2=16$ labelled trees.
The number of labelled graphs isomorphic to a graph $G$ is given by $$\frac{n!}{|\mathrm{Aut}(G)|}$$ where $n$ is the number of vertices of the graph, and $\mathrm{Aut}(G)$ is the automorphism group of the graph. This is a consequence of the Orbit-Stabiliser Theorem. In the above two cases, the automorphism groups have size $6$ (and is isomorphic to $S_3$) and $2$, respectively.
So the $16$ labelled $4$-vertex trees partition into $24/6=4$ trees isomorphic to the tree on the left and $24/2=12$ trees isomorphic to the tree on the right. Since $16=4+12$, we have accounted for all isomorphism classes of trees.
(Note: more than half of the labelled $4$-vertex trees are isomorphic to the graph on the right.)