Counting spanning trees in a complete bipartite graph which contain a given spanning forest

Abstract

In this article, we extend Moon's classic formula for counting spanning trees in complete graphs containing a fixed spanning forest to complete bipartite graphs. Let $(X,Y)$ be the bipartition of the complete bipartite graph $K_{m,n}$ with $|X|=m$ and $|Y|=n$. We prove that for any given spanning forest $F$ of $K_{m,n}$ with components $T_1,T_2,\dots ,T_k$, the number of spanning trees in $K_{m,n}$ which contain all edges in $F$ is equal to $$\frac{1}{mn}\left(\prod _{i=1}^k(m_{i}n+n_{i}m)\right)\left(1-\sum _{i=1}^k\frac{m_i{n}_i}{m_{i}n+n_{i}m}\right),$$ where $m_i=|V(T_i)\cap X|$ and $n_i=|V(T_i)\cap Y|$ for $i=1,2,\dots ,k$.