Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum

Question

For $b,w \geq 0$ let $K_{b+1,w+1}$ be the complete bipartite graph with vertices $a_1,...,a_{b+1}$ on the left hand side and $c_1,...,c_{w+1}$ on the right hand side. For given $1 \leq d \leq w$ and $1 \leq e \leq b$ I want to find the number of spanning trees $t$ of $K_{b+1,w+1}$ with the degrees $d = \deg_t(a_{b+1})$ and $e=\deg_t(c_{w+1})$ such that the edge $(a_{b+1},c_{w+1})$ exists in $t$.

An almost obvious approach would be to remove the edge $(a_{b+1},c_{w+1})$ such that we now have two trees, where we call $t_1$ the one containing $a_{b+1}$ and $t_2$ the one containing $c_{w+1}$. We can now count the number of $t$ by counting the number of possible pairs $(t_1,t_2)$ with $deg_{t_1}(a_{b+1}) = d-1$ and $\deg_{t_2}(c_{w+1}) = e-1$. By doing this under the assumption $d,e>1 \,$ I have arrived at the formula $$ \sum\limits_{k=0}^{m} \sum\limits_{l=0}^{n} {b \choose k} {w \choose l} \frac{k}{n+k-l} {n+k-l \choose k} \, \frac{l}{m-k+l} {m-k+l \choose l} \ , $$ where $m:=b-e+1$, $n:= w-d+1$ and $\frac{0}{0} := 1$.

My question is if some knows of a better way to count these spanning trees or else, if someone can see a way to further simplify the above sum.

Any help is much appreciated!

---

Edit: This image serves as an example to why I have a problem with the current answer. The two spanning trees on the left are different but after the contractions described in the answer they are the same. (It was a problem in my understanding, not the answer.)

Answer 1

This should follow from Kirchoff's formula (and apologies in advance if I made a calculation error below). What you're asking for is the number of spanning trees that can be obtained by contracting along $e=(a_{b+1},c_{w+1})$ such that this new vertex has exactly $d-1$ additional edges to the remaining $w$ right vertices and $e-1$ additional edges to remaining $b$ left vertices. There are exactly ${w \choose d-1}{b \choose e-1}$ choices of such edges, and by symmetry, all such choices have the same number of spanning trees containing them so we may count those. To count the number of spanning trees containing any such fixed choice of these edges, contract again along those edges. The resulting graph is the union of $K_{b-e+1,w-d+1}$ and the contracted vertex $v$ which has $d$ edges to each right vertex and $e$ edges to each left vertex. To avoid spanning trees that have additional edges that are the image of edges from $a_{b+1}$ and $c_{w+1}$ in the contraction (as we already chose all edges from those vertices), delete those edges so that $v$ now has exactly $d-1$ edges to each left vertex and $e-1$ edges to each right vertex (and a bunch of self-loops that we can also delete).

For convenience, set $\ell=b-e+1$ and $r=w-d+1$. In other words, after relabeling, the adjacency matrix of the contracted graph that we now want to count spanning trees of is \begin{equation*} A = \begin{bmatrix} \mathbf{0}_{\ell\times\ell} & J_{\ell\times r} & (d-1)\mathbf{1}\\ J_{r\times \ell} & \mathbf{0}_{r\times r} & (e-1)\mathbf{1}\\ (d-1)\mathbf{1}^T & (e-1)\mathbf{1}^T & 0 \end{bmatrix}, \end{equation*} where $J$ is the all-ones matrix. By the matrix-tree theorem, it follows that the number of such spanning trees is the determinant of the Laplacian when deleting the last row and column, i.e. \begin{align*} \det\left(\begin{bmatrix} w\mathbf{I}_{\ell\times \ell} & - J_{\ell\times r}\\ -J_{r\times \ell} & b\mathbf{I}_{r\times r} \end{bmatrix}\right) &=\det(w\mathbf{I}_{\ell\times \ell})\det(b\mathbf{I}-J_{r\times \ell}J_{\ell\times r}/w)\\ &=w^{\ell}b^{r-1}(b-\ell r/w)\\&=w^{\ell}b^r-\ell r w^{\ell-1}b^{r-1}, \end{align*} where we use standard block determinant formulas and easily computed eigenvalues.

Recall that this computes the number of spanning trees for each fixed choice of all neighbors of $a_{b+1}$ and $c_{w+1}$. This means the total number of spanning trees should be \begin{equation*} {w \choose d-1}{b \choose e-1}\left(w^{b-e+1}b^{w-d+1}-(b-e+1)(w-d+1)w^{b-e}b^{w-d}\right). \end{equation*}