A problem appeared in a lecture about spanning trees, but we were told to think about it by ourselves.
The complete bipartite graph $K_{m,n}$ is the graph with $m + n$ vertices $a_1,\ldots ,a_m$, $b_1,\ldots ,b_n$ such that there is an edge between each $a_i$ and each $b_j$, but not between any two $a$'s or any two $b$'s. How many spanning trees does $K_{m,n}$ have?
Although, I don't know if it will help, I figured out that $$ \displaystyle \sum_{k=1}^m deg(a_k) = \sum_{k=1}^n deg(b_k) $$ since any edge connected to an $a$ must be connected also to a $b$. Can anyone give a hint on how to solve the problem?
$\endgroup$ 01 Answer
$\begingroup$It’s not an easy problem, and I don’t see a way to give a useful hint, either for the result or for its proof. If you’d like to try proving it, the answer is that there are $m^{n-1}n^{m-1}$ spanning trees. The easiest proof that I’ve seen is that of Theorem $\bf{1}$ in this paper; it is proved by a completely different technique, involving adjacency and incidence matrices, in this PDF.
$\endgroup$
