Spanning Trees in $K_{m,n}$

Question

Let $K_{m,n}$ be a complete bipartite graph with vertex sets:

$V=\{a_1,a_2,...,a_m\}$ and $W=\{b_1,b_2,...,b_n\}$.

$t(K_{m,n})$ denotes the number of spanning trees in $K_{m,n}$.

Prove that $t(K_{2,n})=n*2^{n-1}$

So for $t(K_{2,1})$ clearly there is only 1 solution.

For $t(K_{2,2})$ there are 4 solutions, this is due to both nodes in the set 2, being able to have common neighbor "$a_n$, or $b_n$". Then either only "$a_2$ or $b_2$" will connect to the non-common neighbor.

Answer 1

Hint: Kirchhoff’s Theorem over the Laplacian matrix for $K_{2,n}$: $$L(K_{2,n})=\begin{bmatrix}nI_2&-\boldsymbol{1}_{2\times n}\\-\boldsymbol{1}_{n\times 2}&2I_n\end{bmatrix}.$$

Answer 2

To begin with, this is what $K_{2,n}$ looks like (it's $K_{2,6}$):

Basically, proving this formula boils down to two observations:

1. In a spanning tree, there's exactly one path between the two vertices in the part of size $2$. In this case, they have exactly one common neighbor.

2. Except for this unique common neighbor, every vertex in the part of size $n$ is adjacent to exactly one of the two vertices in the part of size $2$.

So a spanning tree looks like:

Now it's just a matter of counting the ways of doing this.

(For illustration, I've colored the two vertices in the part of size $2$ red and blue, their unique common neighbor white, and the remaining vertices are colored pink if they're adjacent to the red vertex, or light blue if they're adjacent to the blue vertex.)