Prove that the complete bipartite graph $K_{3,s}$ has $s^23^{s-1}$ spanning trees for $s\geq2$

Question

I am wondering about a more combinatorial proof for this question as I have only seen the proof using Kirchoff theorem? Any help would be much appreciated!

Answer 1

More generally, there are $m^{n-1}n^{m-1}$ spanning trees of $K_{m,n}$. Here is a proof which uses generating functions. The proof is long and appears unwieldy, but the result and methods are quite general and beautiful.

---

In $K_{m,n}$, label the vertices of the spanning tree from $v_1$ to $v_m$ in the part of size $m$, and from $v_{m+1}$ to $v_{m+n}$ in the other. We will make a generating function which is a polynomial in the variables $x_1,x_2,\dots,x_{m+n}$. For each spanning tree $T$, define the monomial $x^T$ by $$ x^T=x_1^{\deg(v_1)-1}x_2^{\deg(v_2)-1}\cdots x_{m+n}^{\deg(v_{m+n})-1} $$ The notation $x^T$ is a slight abuse, but it is mnemonic. Then, let $$ P_{n,m}=\sum_T x^T, $$ where $T$ ranges over all spanning subtrees of $K_{m,n}$.

Claim: $P_{n,m}=(x_1+x_2+\dots+x_m)^{n-1}(x_{m+1}+x_{m+2}+\dots+x_{m+n})^{m-1}$.

The fact that there are $m^{n-1}n^{m-1}$ spanning trees follows by setting each $x_i=1$.

Proof: We prove this by induction on $n$ and $m$. Let $$ Q_{n,m}=(x_1+x_2+\dots+x_m)^{n-1}(x_{m+1}+x_{m+2}+\dots+x_{m+n})^{m-1} $$

be the polynomial we claim equals $P_{m,n}$. For each $1\le i\le m+n$, let $$ P_{m,n}^i=\sum_{\substack{T\text{ such that}\\ v_i\text{ is a leaf}}} x^T $$ Note that $P_{m,n}^i$ is exactly the result of setting $x_i=0$ in $P_{m,n}$; when you set $x_i=0$ in $P_{m,n}$, any summands where $\deg v_i\ge 2$ will have a factor of $x_i$, and be killed. I will record this fact as $$ P_{m,n}^i=P_{m,n}\Big|_{x_i=0}\tag1\label1 $$ Now, for the moment, suppose that $i\le m$, so $v_i$ is a vertex in the part of size $m$. And suppose that its neighbor in the other part is $v_{m+j}$, for some $1\le j\le n$. There is an obvious bijection $$ \left\{\; \begin{array}{c}\text{spanning trees of $K_{m,n}$ where }\\\text{$v_i$ is a leaf, with neighbor $v_{m+j}$} \end{array} \;\right\}\iff\{\;\text{spanning trees of $K_{m,n}\setminus \{v_i\}$ }\;\} $$ Both of these are sets of trees, so we take the sum $\sum_T x^T$ for $T$ ranging in either sets. A little thought shows that the sum for the left is equal to $x_{m+j}$ times the sum for the right. Algebraically, $$ \sum_{T\in LHS}x^T=x_{m+j}\sum_{T\in RHS}x^T\tag2\label2 $$ Why? You are summing over basically the same trees, the only difference being that $v_{m+j}$ has an extra neighbor for trees in the LHS. Furthermore, the RHS does not depend on $j$. By induction, the sum of $x^T$ for $T$ in the RHS is just $$ \sum_{T\in RHS}x^T=(x_1+x_2+\dots+\hat x_{i}+\dots+x_m)^{n-1}(x_{m+1}+x_{m+2}+\dots+x_{m+n})^{m-2} $$ where the $\hat{x_i}$ means that $x_{i}$ is omitted from the sum. This is the same as the $$ \sum_{T\in RHS}x^T=(x_1+x_2+\dots+x_m)^{n-1}(x_{m+1}+x_{m+2}+\dots+x_{m+n})^{m-2}\Big|_{x_{i}=0}\tag3\label3 $$ Now, putting this all together, for all $i\le m$, we have \begin{align} P_{m,n}\Big|_{x_i=0} &\stackrel{\eqref1}=P_{m,n}^i \\&=\sum_{\substack{T\text{ such that}\\ v_i\text{ is a leaf}}} x^T \\&=\sum_{j=1}^m\hspace{-1em} \sum_{\substack{T\text{ such that}\\ v_i\text{ is a leaf}\\\text{with neighbor $v_{m+j}$}}}\hspace{-1em} x^T \\&\stackrel{\eqref2}=\sum_{j=1}^mx_{m+j}\sum_{T\text{ spans }K_{m,n}\setminus\{v_i\}}x^T \\&\stackrel{\eqref3}=\left(\sum_{j=1}^mx_{m+j}\right)(x_1+x_2+\dots+x_m)^{n-1}(x_{m+1}+x_{m+2}+\dots+x_{m+n})^{m-2}\Big|_{x_{i}=0} \\&=(x_1+x_2+\dots+x_m)^{n-1}(x_{m+1}+x_{m+2}+\dots+x_{m+n})^{m-1}\Big|_{x_{i}=0} \\&= Q_{m,n}\Big|_{x_{i}=0} \end{align} This is progress! We have not proved that $P_{m,n}=Q_{m,n}$ yet, but we have proved they are equal when you substitute $x_i=0$ in both. This means that $x_i$ is a factor of $P_{m,n}-Q_{m,n}$, for all $1\le i\le m$. You can prove the same is true for $m+1\le i\le m+n$ by the same method. Therefore, we have shown that each variable $x_i$ is a factor of $P_{m,n}-Q_{m,n}$, which implies that the product of all the variables is a factor of $P_{m,n}-Q_{m,n}$.

Now, for the punchline. If $P_{m,n}-Q_{m,n}$ were nonzero, it would have degree at most $m+n-2$, as this is true of both $P_{m,n}$ and $Q_{m,n}$. This would contradict the previous conclusion that the product of all the $x_i$ divides $P_{m,n}-Q_{m,n}$, which would bring the degree up to at least $m+n$. We conclude $P_{m,n}-Q_{m,n}=0$.

Answer 2

Let $S=\{x,y,z\}$ be one set of the bipartition of $K_{3,s}$. Let $T$ be any spanning tree of $K_{3,s}$.

Look first at $x$. Since $T$ is a tree, there exists a unique path $x=v_0, \ldots, v_n=y$ from $x$ to $y$ in $T$. Clearly $v_1$ is in the other set of the bipartition, but $v_2$ must be in $S$.

Case 1: $v_2 = z$. In this case, the path from $x$ to $y$ must look like $x, v_1, z, v_3, y$. To create a spanning tree with this path structure from $x$ to $y$, there are $s$ choices for $v_1$, $s-1$ choices for $v_3$, and the remaining $s-2$ vertices can be attached arbitrarily to the three vertices of $S$ in $3^{s-2}$ ways. Hence there are $(s^2-s) \times 3^{s-2}$ such spanning trees of $K_{3,s}$.

Case 2: $v_2=y$. In this case the path from $x$ to $y$ is $x, v_1, y$, and we consider the path from $x$ to $z$. There are three possible configurations for this path in $T$:

1. $x, v_1, y, v_3, z$: as before, there are $s$ choices for $v_1$ and $s-1$ choices for $v_3$, with the remaining vertices attached to a vertex of $S$ arbitrarily, yielding $(s^2-s) \times 3^{s-2}$ such spanning trees.
2. $x, w_1, z$, where $w_1 \ne v_1$: there are $s$ choices for $v_1$ and $s-1$ choices for $w_1$, and again $3^{s-2}$ ways to attach the remaining vertices, yielding $(s^2-s) \times 3^{s-2}$ such spanning trees
3. $x,v_1,z$: in which all of $x$, $y$ and $z$ are attached to the same vertex. There are $s$ ways to pick $v_1$, and then the remaining $s-1$ vertices can be attached arbitrarily, yielding $s \times 3^{s-1}$ such spanning trees.

Adding up over all of the possibilities, we see there are $$3 \times (s^2-s)\times 3^{s-2} + 3 \times s \times 3^{s-2} = s^2 \times 3^{s-1}$$ spanning trees.

Clearly, this sort of analysis becomes unwieldy for even $K_{4,s}$, let alone the general case. Hopefully it illustrates the power of Kirchoff's theorem over this more simple-minded approach.

Answer 3

Adding a separate answer because I now have a much simpler proof!

---

To prove there are $m^{n-1}n^{m-1}$ spanning trees, we will use a slight modification of Prüfer's original algorithm to get a bijection between trees and integers sequences of length $m+n-2$. Recall that to get a Prufer code, you repeatedly delete the smallest leaf, and record the label of its neighbor. In our case, we will do almost the same; however, instead of always pruning the smallest leaf, we will prune the smallest leaf in a specific part of the bipartite graph.

Specifically, suppose $m\le n$. We will prune leaves from the parts according to the following pattern: $$ \underbrace{\mathsf{N,N,\dots,N}}_{n-m},\underbrace{\mathsf{N,M,N,M\dots,N,M}}_{2(m-1)} $$

So the first string of leaves will come from the larger part, until the parts are equalized, and we alternate thereafter. There are obviously $m^{n-1}n^{m-1}$ possible codes resulting from this pattern, and you can show this procedure is a bijection in a similar way.

How do we know we can always find a leaf in the prescribed part? By this lemma:

Lemma: In the bipartite graph $K_{m,n}$, with $m\le n$, there is a leaf in the part of size $n$.

Proof: The sum of the degrees of the vertices in the $n$ part is equal to the total number of edges, $n+m-1$. If each vertex had degree $2$ or more, this sum of degrees would be at least $2n>n+m-1$. $\square$