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.

  • $\begingroup$ This is straightforward through Kirchoff theorem (en.wikipedia.org/wiki/Kirchhoff%27s_theorem) and Gaussian elimination. $\endgroup$ – Jack D'Aurizio Mar 28 '17 at 1:51
  • $\begingroup$ @JackD'Aurizio Kirchoff's theorem has not been taught in my class, so I can't use it to prove the problem above $\endgroup$ – 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.)

  • $\begingroup$ Could you provide more hints? I'm still lost. $\endgroup$ – user59036 Mar 28 '17 at 6:44
  • $\begingroup$ 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? $\endgroup$ – Misha Lavrov Mar 28 '17 at 11:37
  • $\begingroup$ by $1,2,3,$ are you referring to $u,v w$ vertices? $\endgroup$ – user59036 Mar 29 '17 at 4:07
  • $\begingroup$ Yes, sorry; I forgot the notation I was using in my answer. Read $u$, $v$, $w$ for $1$, $2$, $3$ in the comment above $\endgroup$ – Misha Lavrov Mar 29 '17 at 4:08
  • $\begingroup$ 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? $\endgroup$ – user59036 Mar 29 '17 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.