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.)

enter image description here


1 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*}

  • $\begingroup$ Hello Jason, thanks for the good idea! I'm not sure why the second contraction does not change the number of spanning trees. Suppose both $a_{b-1}$ and $a_{b}$ are contracted into $v$ in this step, then spanning trees which connected to $a_{b-1}$ will not be differentiated from spanning trees which connected to $a_b$. $\endgroup$
    – Tardis
    Jun 30, 2022 at 7:45
  • $\begingroup$ @Tardis I'm not sure I understand your concern, but maybe this helps: because the edges are kept with multiplicity in the contraction (note that Kirchoff works for multigraphs), we can actually distinguish between $a_{b-1}$ and $a_b$'s edges emanating from $v$ (think of labelling the edges in the contracted vertex with the original endpoint). In particular, any spanning tree in the contracted graph should canonically lift to a spanning tree in the full graph. $\endgroup$ Jun 30, 2022 at 20:35
  • $\begingroup$ Sorry for being imprecise. I added a picture above, which should show my misgivings. $\endgroup$
    – Tardis
    Jun 30, 2022 at 22:10
  • $\begingroup$ I think I see your concern, which is that distinct spanning trees might be exactly isomorphic after the contractions. But in the construction above, both (and the other two spanning trees, assuming $d=1$ and $e=3$) really do get counted. Here's how... $\endgroup$ Jun 30, 2022 at 22:28
  • $\begingroup$ The graph after my contractions and deletions of the edges from the bottom nodes in your example graph would be the node $v$ with two edges from $v$ to each of $c_1$ and $c_2$, which correspond to the original edges from $a_1,a_2$ to those two nodes. There are four choices of spanning trees for such a graph (two of which you show), corresponding to $c_1,c_2$ both connecting to $v$ via their $a_1$'s edge (the spanning tree in your first picture), or their $a_2$ edges, or one of each (the second picture with $c_1$ using their $a_1$ edge and $c_2$ connecting to $v$ using the $a_2$ edge). $\endgroup$ Jun 30, 2022 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.