Some Applications of Spanning Trees in $K_{s,t}$

Abstract

We partition the set of spanning trees contained in the complete graph $K_n$ into spanning trees contained in the complete bipartite graph $K_{s,t}$. This classification shows that some properties of spanning trees in $K_n$ can be derived from trees in $K_{s,t}$. We use Abel’s binomial theorem and the formula for spanning trees in $K_{s,t}$ to obtain a proof of Cayley’s theorem using partial derivatives. Some results concerning non-isomorphic spanning trees are presented. In particular, we count these trees for $Q_3$ and the Petersen graph.