Finding non-isomorphic spanning trees How can I find all non-isomorphic spanning trees off complete bipartite graph $K_{3,4}$? I think that there must be 14 non-isomorphic trees, but I don't know how to find it.
 A: Any spanning tree has $6$ edges. Thus, the sum of degrees of the $3$ respectively $4$ edges is $6$.
Thus, the degrees of the $4$ vertices can be $(3,1,1,1)$ or $(2,2,1,1)$. Count them from here.
A: Since the spanning trees are subgraphs of $K_{3,4}$, the degree sequences are of the form $(d_1,d_2,d_3,d_4), (d_5,d_6,d_7)$ where
\begin{align*}
d_1+d_2+d_3+d_4 &= 6, \\
d_5+d_6+d_7 &= 6, \\
d_i & \geq 1 & \text{for all } i \in \{1,\ldots,7\}, \text{ and} \\
d_i & \leq 4 & \text{for all } i \in \{1,\ldots,7\} \\
\end{align*}
This just leaves $(d_1,d_2,d_3,d_4) \in \{(1, 1, 2, 2),(1, 1, 1, 3)\}$ and $(d_5,d_6,d_7) \in \{(1,2,3),(2,2,2)\}$.
Going through the possible degree sequences one by one, we find the following seven spanning trees:

If a spanning tree has $(d_1,d_2,d_3,d_4) = (1, 1, 1, 3)$, then the graph is unique up to isomorphism (the degree-$3$ vertex is adjacent to the three vertices in the other parts, and the neighbors of the degree-$1$ vertices are determined by $(d_5,d_6,d_7)$).  This gives the top row above.
If a spanning tree has $(d_1,d_2,d_3,d_4) = (1, 1, 2, 2)$, then the two degree-$2$ vertices together with their neighbors induce a $5$-vertex path.  We add two degree-$1$ vertices to this in all possible ways, and if we're systematic and careful, we obtain the latter $4$ spanning trees above (1. attach both to the middle of the path, 2. attach both to one end of the path, 3. attach one to one end of the path and one to the middle of the path, 4. attach one to each end of the path).
