Tutorials › Graph Theory (Undergraduate) › Counting Spanning Trees Of Complete Bipartite Graphs

Home  /  Tutorials  /  Spanning Trees and Counting

Spanning Trees and Counting · Tutorial 127 of 799

Counting Spanning Trees Of Complete Bipartite Graphs

Use the matrix-tree theorem and a block determinant to derive and verify the number of spanning trees in \(K_{m,n}\).

Advanced 10 min read

What You'll Learn

  • State the spanning-tree count for \(K_{m,n}\) and its positive-integer assumptions.
  • Form the Laplacian cofactor by deleting a vertex from one part.
  • Evaluate the cofactor using a block determinant and a rank-one matrix.
  • Check the formula on small complete bipartite graphs by independent counts.
  • Recognize and correct a common error in the exponents.

Counting Spanning Trees in a Complete Bipartite Graph

A complete bipartite graph has two vertex classes, with every possible edge between the classes and no edges within either class. Its symmetry makes it a natural setting for the matrix-tree theorem: although the Laplacian grows with the number of vertices, deleting one row and column leaves a block matrix whose determinant can be evaluated systematically. The resulting formula counts spanning trees without listing them individually.

Definition: For positive integers \(m,n\), the complete bipartite graph \(K_{m,n}\) has disjoint vertex classes \(X\) and \(Y\), with \(|X|=m\) and \(|Y|=n\). Its edges are all pairs \(xy\) with \(x\in X\) and \(y\in Y\), and there are no other edges. A spanning tree is a connected, acyclic subgraph containing every vertex of the graph. We write \(t(G)\) for the number of spanning trees of \(G\).

We assume \(m,n\ge 1\), so \(K_{m,n}\) is connected. If one part were empty, the graph would have no edges and, unless it had just one vertex, would have no spanning tree; the formula below is stated for positive part sizes.

For a graph \(G\), its Laplacian is \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), where \(\mathbf{D}\) is the diagonal matrix of vertex degrees and \(\mathbf{A}\) is the adjacency matrix. The matrix-tree theorem states that for a connected graph, the determinant of a matrix obtained by deleting any one row and the corresponding column of \(\mathbf{L}\) equals \(t(G)\). We use this established theorem to turn the counting problem into a determinant calculation.

The Laplacian Cofactor

Every vertex in \(X\) has degree \(n\), and every vertex in \(Y\) has degree \(m\). Order the vertices with the elements of \(X\) first and those of \(Y\) second. Let \(J_{a,b}\) denote the \(a\)-by-\(b\) matrix all of whose entries are \(1\), and let \(I_a\) denote the \(a\)-by-\(a\) identity matrix. The Laplacian has block form

$$ \mathbf{L}(K_{m,n})= \begin{pmatrix} nI_m & -J_{m,n}\\ -J_{n,m} & mI_n \end{pmatrix}. $$

Delete the row and column for one vertex of \(Y\). The remaining cofactor matrix is

$$ \mathbf{L}^{*}= \begin{pmatrix} nI_m & -J_{m,n-1}\\ -J_{n-1,m} & mI_{n-1} \end{pmatrix}. $$

If \(n=1\), the lower-right block has size zero, and the cofactor is simply \(I_m\). Its determinant is \(1\), agreeing with \(m^{0}1^{m-1}=1\). For \(n\ge2\), we evaluate the determinant using the following block determinant fact.

Lemma: If \(D\) is an invertible square matrix, then \(\det\begin{pmatrix}A&B\\C&D\end{pmatrix}=\det(D)\det(A-BD^{-1}C)\), provided the blocks have compatible sizes.

Proof. Multiply the block matrix on the left by \(\begin{pmatrix}I&-BD^{-1}\\0&I\end{pmatrix}\). This multiplier has determinant \(1\), since it is block triangular with identity diagonal blocks. The product is \(\begin{pmatrix}A-BD^{-1}C&0\\C&D\end{pmatrix}\), a block triangular matrix. Its determinant is \(\det(A-BD^{-1}C)\det(D)\), which proves the identity. \(\square\)

Apply the lemma with \(D=mI_{n-1}\), which is invertible because \(m\ge1\). The product \(J_{m,n-1}J_{n-1,m}\) has every entry equal to \(n-1\), so it is \((n-1)J_{m,m}\). Therefore

$$ \det(\mathbf{L}^{*}) =m^{n-1}\det\left(nI_m-\frac{n-1}{m}J_{m,m}\right). $$

To evaluate the remaining determinant, let \(\mathbf{1}\) be the vector of \(m\) ones. The matrix \(J_{m,m}\) sends \(\mathbf{1}\) to \(m\mathbf{1}\), and sends every vector whose coordinates sum to zero to the zero vector. Thus \(nI_m-\frac{n-1}{m}J_{m,m}\) sends \(\mathbf{1}\) to \(\mathbf{1}\), and acts as multiplication by \(n\) on the \((m-1)\)-dimensional space of vectors whose coordinates sum to zero. These spaces together span the \(m\)-dimensional vector space, including when \(m=1\), when the second space has dimension zero. The determinant is consequently \(1\cdot n^{m-1}=n^{m-1}\).

Theorem: For positive integers \(m,n\), the number of spanning trees of the complete bipartite graph \(K_{m,n}\) is $$ t(K_{m,n})=m^{\,n-1}n^{\,m-1}. $$

Proof. If \(n=1\), the cofactor described above is \(I_m\), so the matrix-tree theorem gives \(t(K_{m,1})=1=m^0 1^{m-1}\). If \(n\ge2\), the block determinant calculation gives \(\det(\mathbf{L}^{*})=m^{n-1}n^{m-1}\). Since \(K_{m,n}\) is connected, the matrix-tree theorem identifies this cofactor determinant with its spanning-tree count. Both cases give the stated formula. \(\square\)

The formula is unchanged if the two parts are interchanged: \(m^{n-1}n^{m-1}=n^{m-1}m^{n-1}\). The exponents, however, are attached to the opposite part sizes: the base \(m\) has exponent \(n-1\), and the base \(n\) has exponent \(m-1\). The examples below check both the cofactor calculation and the count by a separate structural argument.

Worked Example: The Star \(K_{1,3}\)

Let \(X=\{x\}\), \(Y=\{y_1,y_2,y_3\}\), and let \(E=\{xy_1,xy_2,xy_3\}\). The formula gives \(t(K_{1,3})=1^{3-1}3^{1-1}=1^2\cdot3^0=1\).

For a cofactor calculation, delete \(y_3\). In the order \(x,y_1,y_2\), the cofactor matrix and its determinant are

$$ \begin{pmatrix} 3&-1&-1\\ -1&1&0\\ -1&0&1 \end{pmatrix}, \qquad 3(1\cdot1-0\cdot0)-(-1)(-1\cdot1-0\cdot(-1)) +(-1)((-1)\cdot0-1\cdot(-1))=3-1-1=1. $$

Check: The graph is already a tree: it is connected, and its three edges are all required to connect the three leaves to \(x\). Thus it has exactly one spanning tree, agreeing with the determinant and the formula.

Worked Example: The 4-Cycle \(K_{2,2}\)

Let \(X=\{x_1,x_2\}\), \(Y=\{y_1,y_2\}\), and \(E=\{x_1y_1,x_1y_2,x_2y_1,x_2y_2\}\). The formula gives \(t(K_{2,2})=2^{2-1}2^{2-1}=2\cdot2=4\).

Delete \(y_2\) and order the remaining vertices as \(x_1,x_2,y_1\). The cofactor determinant is

$$ \det\begin{pmatrix} 2&0&-1\\ 0&2&-1\\ -1&-1&2 \end{pmatrix} =2(2\cdot2-(-1)(-1))+(-1)(0\cdot(-1)-2(-1)) =2(3)-2=4. $$

Check: The four edges form a 4-cycle. A spanning tree is obtained by deleting exactly one of the four edges; each of the four choices leaves a connected path on all four vertices. Each such path is acyclic, and a spanning tree on four vertices has three edges. Hence there are exactly \(4\) spanning trees, independently confirming the formula.

Worked Example: Counting Spanning Trees of \(K_{2,3}\)

Let \(X=\{x_1,x_2\}\), \(Y=\{y_1,y_2,y_3\}\), and \(E=\{x_iy_j: i\in\{1,2\},\ j\in\{1,2,3\}\}\). The graph has six edges. The formula gives \(t(K_{2,3})=2^{3-1}3^{2-1}=2^2\cdot3=4\cdot3=12\).

Delete \(y_3\), and order the remaining vertices as \(x_1,x_2,y_1,y_2\). The cofactor is

$$ \begin{pmatrix} 3&0&-1&-1\\ 0&3&-1&-1\\ -1&-1&2&0\\ -1&-1&0&2 \end{pmatrix}. $$

Using the block determinant calculation, the lower-right block \(2I_2\) has determinant \(4\). The remaining block is \(3I_2-\frac12J_{2,2}J_{2,2}^{T}=3I_2-J_{2,2}=\begin{pmatrix}2&-1\\-1&2\end{pmatrix}\), whose determinant is \(2\cdot2-(-1)(-1)=3\). The full determinant is \(4\cdot3=12\).

Check by an independent count: A spanning tree on five vertices has four edges, so a four-edge subgraph is specified by the two of the six edges that it omits. There are \(\binom{6}{2}=15\) possible omitted pairs. If both edges incident with some \(y_j\) are omitted, that vertex is isolated, so the subgraph is disconnected. There are three such pairs, one for each \(y_j\), and no pair isolates two vertices. Every other omitted pair leaves a connected graph: with only two edges removed, at least one of the three vertices in \(Y\) still has both incident edges, joining \(x_1\) to \(x_2\); every other \(y_j\) has at least one remaining edge and so joins this connected pair. Thus \(15-3=12\) subgraphs are connected. Each has five vertices and four edges, hence is a tree. This independently gives \(12\).

Common Pitfall: Swapping the Exponents

A frequent error is to pair each part size with the exponent from its own part. That gives the incorrect expression \(m^{m-1}n^{n-1}\). For \(K_{2,3}\), this mistaken expression gives \(2^{2-1}3^{3-1}=2\cdot9=18\), contradicting both the cofactor calculation and the direct count above. The correct exponents are opposite the bases: the \(m\)-factor has exponent \(n-1\), while the \(n\)-factor has exponent \(m-1\). Substituting \(m=2,n=3\) gives \(2^{3-1}3^{2-1}=4\cdot3=12\).

The matrix-tree approach is useful here because it turns the symmetry of \(K_{m,n}\) into repeated rows and columns in a cofactor, then reduces the determinant to two simple actions: one on the all-ones vector and one on vectors with coordinate sum zero. It also provides a check against direct enumeration on small graphs. For larger part sizes, the same cofactor structure yields the count without requiring a list of candidate trees.

Check Your Understanding

Use the cofactor structure and the formula to justify your answers.

  1. How many spanning trees does \(K_{1,5}\) have? Explain why the graph structure gives the same count.
  2. Evaluate the formula for \(K_{2,4}\), showing the value of each power before multiplying.
  3. For \(K_{3,3}\), which two eigenvalues of the reduced \(3\)-by-\(3\) block occur, and with what multiplicities?
  4. Why does deleting one vertex from the part of size \(n\) leave an \(m\)-by-\(m\) block \(nI_m\) in the cofactor?
  5. Identify the error in using \(m^{m-1}n^{n-1}\) for the spanning-tree count of \(K_{m,n}\).

Previous

Next

Back to Tutorials