Fdtxjr

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!

More generally, there are $m^n-1n^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)-1x_2^deg(v_2)-1cdots 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-1n^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 $1le ile m+n$, let
$$
P_m,n^i=sum_substackTtext such that\ v_itext 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_ige 2$ will have a factor of $x_i$, and be killed. I will record this fact as
$$
P_m,n^i=P_m,nBig|_x_i=0tag1label1
$$
Now, for the moment, suppose that $ile 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 $1le jle n$. There is an obvious bijection
$$
left;
beginarrayctextspanning trees of $K_m,n$ where \text$v_i$ is a leaf, with neighbor $v_m+j$
endarray
;rightiff;textspanning trees of $K_m,nsetminus 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_Tin LHSx^T=x_m+jsum_Tin RHSx^Ttag2label2
$$
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_Tin RHSx^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 $hatx_i$ means that $x_i$ is omitted from the sum. This is the same as the
$$
sum_Tin RHSx^T=(x_1+x_2+dots+x_m)^n-1(x_m+1+x_m+2+dots+x_m+n)^m-2Big|_x_i=0tag3label3
$$
Now, putting this all together, for all $ile m$, we have
beginalign
P_m,nBig|_x_i=0
&stackreleqref1=P_m,n^i
\&=sum_substackTtext such that\ v_itext is a leaf x^T
\&=sum_j=1^mhspace-1em sum_substackTtext such that\ v_itext is a leaf\textwith neighbor $v_m+j$hspace-1em x^T
\&stackreleqref2=sum_j=1^mx_m+jsum_Ttext spans K_m,nsetminusv_ix^T
\&stackreleqref3=left(sum_j=1^mx_m+jright)(x_1+x_2+dots+x_m)^n-1(x_m+1+x_m+2+dots+x_m+n)^m-2Big|_x_i=0
\&=(x_1+x_2+dots+x_m)^n-1(x_m+1+x_m+2+dots+x_m+n)^m-1Big|_x_i=0
\&= Q_m,nBig|_x_i=0
endalign
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 $1le ile m$. You can prove the same is true for $m+1le ile 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$.

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.

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

To prove there are $m^n-1n^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 $mle n$. We will prune leaves from the parts according to the following pattern:
$$
underbracemathsfN,N,dots,N_n-m,underbracemathsfN,M,N,Mdots,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-1n^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 $mle 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$