Prove the number of spanning trees of $K_{3,m}$ is $3^{m−1}m^2$.
Based on the definition of a bipartite graph, each of the $3$ vertices has degree $m$, and each of the $m$ vertices has degree $3$. The total number of vertices is $3+m$, so each of the spanning trees has $3+m$ vertices. I also know that a graph is bipartite if and only if it has no odd cycles.
Intuitively, I feel this proof is a combinatoric problem, but I just couldn't figure out how to proceed. Thanks in advance for any hints.
Hint: For each of the $m$ vertices on the let's-call-it-right-hand side, we should pick a nonempty subset of the left-hand vertices $u,v,w$ to be its neighbors. For the most part, that subset will just be $\{u\}$, $\{v\}$, or $\{w\}$: we would get $3^m$ if all $m$ vertices looked like this.
If all vertices looked like this, the subgraph would still be disconnected and not be a spanning tree. So we have to tweak a few of the vertices to do something different. Not too many: for example, if $x$ and $y$ on the right-hand side are given $\{u,v\}$ for neighbors, then we have a cycle $(x,u,y,v,x)$.
Consider all possible ways we can pick "exceptional" vertices on the right-hand side to have more than one neighbor, and how to count them. (We want enough exceptional vertices to connect the subgraph, but not enough to create cycles.)