count spanning trees (up to isomorphism) in K3,3

Question

I look through the solution posted on stackexchange about counting spanning trees in K3,3 (the link is here Number of spanning trees of $K_{3,3}$.). But I am still confused about how to count it by adding condition "isomorphism", since in that post, based on my understanding the answer seems to consider two isomorphic spanning trees as two different spanning tree (say we let $a_1$, $a_2$, $a_3$ belong to group A in this bipartite, and $b_1$, $b_2$, $b_3$ belong to group B, then in the above answer, $a_1\rightarrow b_1\rightarrow a_3\rightarrow b_2\rightarrow a_2\rightarrow b_3$ and $b_3\rightarrow a_3\rightarrow b_1\rightarrow a_2\rightarrow b_2\rightarrow a_1$ are two spanning trees; but they seem to be isomorphic if we define f to let $a_1$ in first spanning tree to be $b_3$ in second spanning tree, $b_1$ in first spanning tree to be $a_3$ in second spanning tree, and so on). Can anyone mention how to solve it or just some hints? Also, if my understanding is wrong, please inform me in which step I am wrong! Thanks!

Answer 1

I think the best way to do this is to consider the possible degree sequences (the sequence of vertex degrees) of a spanning tree. A spanning tree of $K_{3,3}$ has $6$ vertices and so $5$ edges. The sum of the vertex degree is therefore $10$. Each vertex in the tree has degree between $1$ and $3$, so the only possible degree sequences are:$$3,3,1,1,1,1\\3,2,1,1,1,1\\2,2,2,2,1,1\\$$

Now you have to consider what graphs with these degree sequences can be spanning trees. Consider the last one. There are several graphs with this degree sequence, for example a path of length $1$ and a $4$-cycle, or a path of length $2$ and a $3$-cycle, but the only connected graph is a path of length $5$. This is the spanning tree you mentioned, and all paths of length $5$ are isomorphic, so this degree sequence leads to exactly one isomorphism class of spanning trees.

I leave it to you to investigate the other two.