Enumerating spanning trees

In 1889 Arthur Cayley stated his well-known and widely used theorem that there are n° - 2 trees on n labeled vertices [6, p. 70]. Since he originally stated it, the theorem has received much attention: people have proved it in many different ways. In this paper we consider three of these proofs. The first is an algebraic . result using Kirchhoff s Matrix Tree theorem. The second proof shows a one-to-one correspondence between trees on labeled vertices and sequences known as Prufer codes. The final proof involves degree sequences and multinomial coefficients. In addition, we extend each of these three proofs to find a result for the number·of spanning trees on the complete bipartite graph, and extend the first two results to count the number of spanning trees on the complete tripartite graph. We conclude with a brief generalization to the number of spanning trees on the complete k-partite graph.