Finding non-isomorphic spanning trees

2k Views Asked by At

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.

1

There are 1 best solutions below

1
On

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.