Why Complete Graphs Are a Useful Test Case
A complete graph has an edge between every pair of distinct vertices. Its symmetry makes its Laplacian especially simple, but its spanning-tree count still grows quickly: the complete graph on \(n\) labeled vertices has \(n^{n-2}\) spanning trees when \(n\ge 2\). We derive this count by computing a principal cofactor of the Laplacian. The derivation also shows exactly why the cofactor has a different eigenvalue structure from the full Laplacian.
We use the Matrix-Tree Theorem, established in the earlier material on Laplacian cofactors: if \(G\) is a connected graph with Laplacian \(\mathbf L\), then deleting the same row and column from \(\mathbf L\) gives a matrix whose determinant is \(t(G)\). We will calculate that determinant for \(K_n\). Since \(K_n\) is connected for every \(n\ge1\), the theorem applies; when \(n=1\), the cofactor is the empty matrix and its determinant is \(1\).
The Laplacian and Its Cofactor
The 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. For \(K_n\), every vertex has degree \(n-1\). Let \(\mathbf I_n\) denote the \(n\)-by-\(n\) identity matrix and \(\mathbf J_n\) the \(n\)-by-\(n\) matrix whose entries are all \(1\). The adjacency matrix of \(K_n\) is \(\mathbf J_n-\mathbf I_n\), so
Deleting the last row and column leaves an \((n-1)\)-by-\((n-1)\) matrix. If \(\mathbf J_{n-1}\) is the all-ones matrix of that size, this cofactor matrix is
Proof. Let \(\mathbf 1\) be the vector of \(n-1\) entries all equal to \(1\). Multiplication by \(\mathbf J_{n-1}\) sends any vector to the vector whose entries are all the sum of the original entries. In particular, \(\mathbf J_{n-1}\mathbf 1=(n-1)\mathbf 1\). Therefore \(\mathbf C_n\mathbf 1=(n-(n-1))\mathbf 1=\mathbf 1\), so \(1\) is an eigenvalue.
Now take any vector \(x\) whose \(n-1\) entries sum to \(0\). Then \(\mathbf J_{n-1}x=0\), and consequently \(\mathbf C_nx=nx\). The space of such vectors has dimension \(n-2\): it is the solution space of one nonzero linear equation in \(n-1\) coordinates. Every vector in \(\mathbb R^{n-1}\) is a sum of a multiple of \(\mathbf 1\) and a vector whose coordinates sum to \(0\), because subtracting the mean of its coordinates leaves a sum-zero vector. These spaces therefore account for all \(n-1\) dimensions. In a basis formed from these eigenvectors, the matrix is diagonal, with one diagonal entry \(1\) and \(n-2\) entries \(n\). Its determinant is their product, \(1\cdot n^{n-2}=n^{n-2}\). For \(n=2\), the sum-zero subspace has dimension \(0\), so the same calculation gives determinant \(1\). \(\square\)
Proof. For \(n\ge2\), \(K_n\) is connected, so the Matrix-Tree Theorem says that \(t(K_n)=\det(\mathbf C_n)\), where \(\mathbf C_n\) is the principal cofactor matrix obtained by deleting one row and the corresponding column of its Laplacian. The lemma gives \(\det(\mathbf C_n)=n^{n-2}\), proving the formula. For \(K_1\), the graph has one vertex and no edges. The subgraph containing that vertex and no edges is a tree, and it is the only spanning subgraph, so \(t(K_1)=1\). \(\square\)
The full Laplacian offers a useful comparison. From \(\mathbf L(K_n)=n\mathbf I_n-\mathbf J_n\), the all-ones vector is an eigenvector with eigenvalue \(0\), while every vector whose coordinates sum to \(0\) has eigenvalue \(n\). Thus the full Laplacian has eigenvalues \(0\) once and \(n\) with multiplicity \(n-1\). The cofactor calculation is not the product of all these eigenvalues: the full determinant is zero. Deleting a row and column produces the matrix \(\mathbf C_n\), with eigenvalues \(1,n,\dots,n\), whose determinant is the spanning-tree count.
Worked Counts
Worked Example: The Triangle \(K_3\)
Let \(V=\{1,2,3\}\) and \(E=\{12,13,23\}\). Every vertex has degree \(2\), so the Laplacian and the cofactor obtained by deleting row \(3\) and column \(3\) are
Its determinant is \(2\cdot2-(-1)(-1)=4-1=3\). Thus \(t(K_3)=3\). For an independent check, a spanning tree on three vertices must use two of the triangle’s three edges: using two connects all three vertices and creates no cycle. There are \(\binom{3}{2}=3\) such choices, agreeing with the cofactor.
Worked Example: The Complete Graph \(K_4\)
Let \(V=\{1,2,3,4\}\) and \(E=\{ij:1\le i<j\le4\}\). Each vertex has degree \(3\). Deleting the fourth row and column of the Laplacian gives
The all-ones vector is an eigenvector with eigenvalue \(3-2=1\). The two-dimensional space of vectors whose three coordinates sum to \(0\) has eigenvalue \(3-(-0)=3\) if computed as \(3\mathbf I-\mathbf J\) on that space; however, here the diagonal entries are \(3\) and the off-diagonal entries are \(-1\), so the matrix is \(4\mathbf I_3-\mathbf J_3\). Its eigenvalue on the all-ones vector is \(4-3=1\), and on the sum-zero space it is \(4\). Therefore the determinant is \(1\cdot4\cdot4=16\), so \(t(K_4)=16\).
Check independently using Prüfer sequences: the established bijection between labeled trees on four vertices and sequences of length \(4-2=2\) over the four labels gives \(4\cdot4=16\) trees. This matches the cofactor calculation.
Worked Example: The Complete Graph \(K_5\)
Let \(V=\{1,2,3,4,5\}\) and \(E=\{ij:1\le i<j\le5\}\). Every vertex has degree \(4\). Deleting the fifth row and column gives the cofactor matrix
The all-ones vector has eigenvalue \(5-4=1\). The subspace of four-coordinate vectors whose entries sum to \(0\) has dimension \(3\), and each of its vectors has eigenvalue \(5\). Hence \(\det(\mathbf C_5)=1\cdot5\cdot5\cdot5=125\), and \(t(K_5)=125\).
As a separate check, Prüfer sequences for five labeled vertices have length \(5-2=3\). Each of the three positions can contain any of the five labels, giving \(5\cdot5\cdot5=125\) sequences. The Prüfer bijection therefore gives the same count.
Common Pitfall: Using the Full Laplacian Determinant
A frequent error is to use the eigenvalues of the full Laplacian as though their product were the spanning-tree count. For \(K_4\), those eigenvalues are \(0,4,4,4\), so their product is \(0\), not \(16\). The zero is expected: every Laplacian has row sums \(0\), so its rows are linearly dependent. The Matrix-Tree Theorem uses a principal cofactor, not the determinant of the full Laplacian.
A second error is to assume that every eigenvalue of the cofactor is \(n\). For \(K_4\), this would give \(4^3=64\), which is incorrect. The cofactor matrix is \(4\mathbf I_3-\mathbf J_3\), not \(4\mathbf I_3\). On the all-ones vector, \(\mathbf J_3\) acts by multiplication by \(3\), so the cofactor has eigenvalue \(4-3=1\); only the two sum-zero directions have eigenvalue \(4\). The correct product is \(1\cdot4\cdot4=16\).
The complete-graph calculation illustrates a useful pattern: symmetry can make a matrix easy to analyze by separating the all-ones direction from the vectors whose coordinates sum to zero. Here that separation turns the cofactor determinant into one small eigenvalue and a repeated eigenvalue. The Matrix-Tree Theorem then converts that determinant into a count of spanning trees.
Check Your Understanding
For each question, distinguish the full Laplacian from the cofactor used by the Matrix-Tree Theorem.
- Write \(\mathbf L(K_6)\) in terms of \(\mathbf I_6\) and \(\mathbf J_6\), and state its eigenvalues with multiplicities.
- For \(K_3\), explain why the cofactor eigenvalues are \(1\) and \(3\), rather than \(2\) and \(2\).
- Use the cofactor method to find \(t(K_2)\), and verify the answer from its edge set.
- Explain why the determinant of the full Laplacian of \(K_5\) is zero even though \(K_5\) has spanning trees.
- For \(K_7\), state the size of the sum-zero subspace in the cofactor and use it to calculate the spanning-tree count.