number of spanning tree of $K(3,5)$

Question

A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. I need number of spanning tree of $K(3,5)$ where $k$ is bipartite complete graph. Can you help me?

Answer 1

Do you know Kirchhoff's theorem? If you do, it is not very difficult. Otherwise, you can find a combinatorial proof that $K_{m,n}$ has $m^{n-1}n^{m-1}$ spanning trees from this paper (or here). I also found another paper with the proof of Kirchoff's theorem and a different proof of the same result. In particular, for $(m,n)=(3,5)$, there are $3^{5-1}5^{3-1}=2025$ spanning trees of $K_{3,5}$.

WLOG, let the vertices of $K_{m,n}$ be $1,2,\ldots,m+n$. The vertex bipartition is $$\{1,2,\ldots,m\}\cup\{m+1,m+2,\ldots,n\}.$$

Let $D$ be the degree matrix of $$D=\operatorname{diag}(\underbrace{n,n,\ldots,n}_{m\text{ copies}},\underbrace{m,m,\ldots,m}_{n\text{ copies}}).$$ We take $J_{p,q}$ to the $p\times q$ matrix all of whose entries are $1$. Let $A$ be the adjacency matrix $$A=\begin{pmatrix}0&J_{m,n}\\ J_{n,m}&0\end{pmatrix}.$$

The Laplacian matrix $L$ is given by $D-A$, so $$L=\begin{pmatrix}nI_m&-J_{m,n}\\-J_{n,m}&mI_n\end{pmatrix}.$$ We must remove the last row and column of $L$ to get $$Q=\begin{pmatrix}nI_m&-J_{m,n-1}\\-J_{n-1,m}&mI_{n-1}\end{pmatrix}.$$ The matrix $Q$ is an $(m+n-1)\times (m+n-1)$ matrix. I claim that the eigenvalues of $Q$ are $1$, $n-1$ copies of $m$, and $m-1$ copies of $m$.

First, $$EQ=\begin{pmatrix}nI_m&-J_{m,n}\\0&-\frac{m}{n}J_{n-1,n-1}+I_{n-1}\end{pmatrix}$$ where $$E=\begin{pmatrix}I_m&0\\\frac{1}{n}J_{n-1,m}&I_{n-1}\end{pmatrix}.$$ Since $\det E=1$, we have $$\det Q=\det(EQ)=\det (nI_m)\det\left(-\frac{m}{n}J_{n-1,n-1}+mI_{n-1}\right).$$ It is not difficult to see that $$\det\left(-\frac{m}{n}J_{n-1,n-1}+mI_{n-1}\right)=\frac{m^{n-1}}{n},$$ since $m$ is an eigenvalue of $-\frac{m}{n}J_{n-1,n-1}+mI_{n-1}$ with multiplicity $n-2$, and the other eigenvalue is $$\operatorname{Tr}\left(-\frac{m}{n}J_{n-1,n-1}+mI_{n-1}\right)-m(n-2)=\frac{m}{n}.$$ Thus, $$\det Q=\det (nI_m)\det\left(-\frac{m}{n}J_{n-1,n-1}+mI_{n-1}\right)=n^m\left(\frac{m^{n-1}}{n}\right)=m^{n-1}n^{m-1}.$$ By Kirchhoff's theorem, there are $m^{n-1}n^{m-1}$ spanning trees of $K_{m,n}$.