Number of trees on $n+k$ vertices that do not contain edges that are only between first $n$ vertices

Question

So say I have $n$ black vertices $\{x_1,\dots,x_n\}$ and $k$ white vertices $\{y_1,\dots,y_k\}$, I want to count the number of trees that do not contain any edge of the type $(x_i,x_j)$. I have calculated the number using inclusion-exclusion and the formula in Lemma 6 from this paper (DOI link) for the case $n=2,3,4$ and I think the number should be equal to $k^{n-1}(k+n)^{k-1}$, it does however get very complicated and I wonder if there is an easier way to show this.

Answer 1

This is equivalent to counting the number of spanning trees of $K_{n+k} - K_n$ (where we start with a complete graph on $n+k$ vertices, and delete all edges between the first $n$ vertices). The Laplacian matrix of this graph, in block form, is $$ \begin{bmatrix} k I_n & -J_{n \times k} \\ -J_{k \times n} & (n+k)I_k - J_{k \times k} \end{bmatrix} $$ where $I_m$ is the $m \times m$ adjacency matrix, and $J_{s \times t}$ is the $s \times t$ matrix of all ones.

We can apply Kirchhoff's matrix tree theorem to count the spanning trees. First, delete the first row and column, getting $$ \begin{bmatrix} k I_{n-1} & -J_{n-1 \times k} \\ -J_{k \times n-1} & (n+k)I_k - J_{k \times k} \end{bmatrix} $$ Next, use the formula $\det(A) \det(D - CA^{-1}B)$ to simplify: we get $$ \det(k I_{n-1}) \det((n+k)I_k - J_{k \times k} - J_{k\times n-1}( \tfrac1k I_{n-1}) J_{n-1 \times k}). $$ First, $\det(k I_{n-1})$ simplifies to $k^{n-1}$. In the second, more complicated determinant, $J_{k\times n-1}( \tfrac1k I_{n-1}) J_{n-1 \times k}$ becomes $\frac{n-1}{k} J_{k \times k}$, so altogether we get $(n+k)I_k - \frac{n+k-1}{k} J_{k \times k}$. To find this determinant, note that:

• $J_{k \times k}$ has eigenvalues $k, 0, 0, \dots, 0$.
• Therefore $-\frac{n+k-1}{k}J_{k \times k}$ has eigenvalues $-(n+k-1), 0,0,\dots,0$.
• Adding $(n+k)I_k$ adds $n+k$ to all eigenvalues, giving us $1, n+k, n+k, \dots, n+k$.
• The determinant is the product of all these eigenvalues: $(n+k)^{k-1}$.

This results in the overal formula $k^{n-1}(n+k)^{k-1}$, as you conjectured.

---

This is a special case of a formula for complete multipartite graphs, which has apparently been both rediscovered and re-proved multiple times. One source is "The number of spanning trees of a complete multipartite graph" by Richard Lewis, which gives a proof by a Prüfer sequence-type argument. The formula is that if $n_1 + n_2 + \dots + n_k = n$, then $K_{n_1, n_2, \dots, n_k}$ has $$ n^{k-2} \prod_{i=1}^k (n-n_i)^{n_i-1} $$ spanning trees.

Here, the graph $K_{n+k} - K_n$ can be rewritten as the complete $(k+1)$-partite graph $K_{n,1,1,\dots,1}$, and so the formula gives us $$ (n+k)^{k-1} k^{n-1} (n+k-1)^0 (n+k-1)^0 \cdots (n+k-1)^0. $$ After leaving out all the factors which simplify to $1$, this gives us the same result.