# Prove the number of spanning trees of $K_{3,m}$ is $3^{m−1}m^2$.

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.

• This is straightforward through Kirchoff theorem (en.wikipedia.org/wiki/Kirchhoff%27s_theorem) and Gaussian elimination. – Jack D'Aurizio Mar 28 '17 at 1:51
• @JackD'Aurizio Kirchoff's theorem has not been taught in my class, so I can't use it to prove the problem above – user59036 Mar 28 '17 at 6:41

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.)

• Could you provide more hints? I'm still lost. – user59036 Mar 28 '17 at 6:44
• We can connect the vertices either by choosing a $\{1,2\}$ vertices and a $\{2,3\}$ vertex, or a $\{1,3\}$ vertex and a $\{2,3\}$ vertex, or a $\{1,2\}$ vertex and a $\{1,3\}$ vertex, or a $\{1,2,3\}$ vertex. Are you okay counting each of these? – Misha Lavrov Mar 28 '17 at 11:37
• by $1,2,3,$ are you referring to $u,v w$ vertices? – user59036 Mar 29 '17 at 4:07
• Yes, sorry; I forgot the notation I was using in my answer. Read $u$, $v$, $w$ for $1$, $2$, $3$ in the comment above – Misha Lavrov Mar 29 '17 at 4:08
• I still don't understand what you mean. You said in the comments above that "we can connect the vertices either by choosing a ${1,2}$ vertex and a ${2,3}$ vertex." Aren't these two vertices in the same set? How do you connect them? – user59036 Mar 29 '17 at 19:02