Hi all, for a Graph with vertex set {1,..., n} we have that the number of spanning trees is equal to n^{n-2}, which is Cayley's formula.

Wikipedia says that for the complete bipartite graph K_{n,m} this number is equal to m^{n-1}n^{m-1}, as a consequence of Cayley's Theorem.

I'm sure there's a simple combinatoric argument involved here...but I don't see how it follows. Any ideas?