Proof $K_3,_n$ is $n^2 3^{n-1}$ The number of spanning trees of $K_3,_n$ is $n^2 3^{n-1}$, this is true if we try by induction for any $n$ ( with n = 4, 5, . . .). is it true ??
How to prove  $K_3,_n$ is $n^2 3^{n-1}$ ?? 
 A: The number of edges is $3n$, and we need $n+2$ edges in the spanning tree. Consider the degree of the $n$ vertices (in the second partite set) in the spanning tree. We now split into cases.
As every edge joins the $2$ partite sets, the sum of the degrees in the second partite set is $n+2$. Every vertex has degree $\geq1$, so there are only the $2$ cases listed below.
Case 1: One vertex in the second partite set has degree $3$.
All other vertices have degree $1$. There are $n$ ways to choose the vertex with degree $3$, $3^{n-1}$ ways to choose which vertex among the $3$ in the first partite set the other $n-1$ vertices connect to.
Case 2: No vertex has degree $3$ in the second partite set, two vertices have degree $2$.
There are $n$ ways to select the first vertex with degree $2$, and $3$ ways of selecting the neighbours of that vertex. There are $n-1$ ways to select the second vertex with degree $2$, and the first vertex and second vertex need to share one neighbour, so there are $2$ ways of selecting the neighbour. Since the first vertex and second vertex can be selected in any order, we overcounted by a factor of $2$. The other $n-2$ vertices can choose any neighbour in the first partite set to connect to.
Hence there are $n3^{n-1}+\frac{n(n-1)\times3\times2}{2}\times3^{n-2}=n^23^{n-1}$ spanning trees.
