Graph Laplacians And Their Cofactors

From a Graph to Its Laplacian

The adjacency matrix records which pairs of vertices are joined by edges. The Laplacian adds degree information along its diagonal, producing a matrix whose rows balance exactly: the diagonal entry in a row equals the number of adjacent vertices, and each such neighbor contributes a \(-1\). This balance gives every Laplacian a zero row sum. It also provides a useful starting point for determinant calculations involving graphs.

Throughout, graphs are finite and simple, and their edges are undirected. Choose and fix an ordering \(v_1,\dots,v_n\) of the vertices. The adjacency matrix \(\mathbf{A}(G)\) has entry \(1\) in position \(i,j\) when \(v_i v_j\in E(G)\), and entry \(0\) otherwise. The degree matrix \(\mathbf{D}(G)\) is diagonal, with entry \(\deg(v_i)\) in position \(i,i\).

The diagonal entry records the degree, not the adjacency entry: in a simple graph \(A_{ii}=0\), so \(L_{ii}=\deg(v_i)\). An isolated vertex has degree zero and gives a zero row and column. Because the graph is undirected, \(\mathbf{L}(G)\) is symmetric.

Proof. Fix a vertex \(v_i\). In row \(i\), the diagonal entry is \(\deg(v_i)\). There is one entry \(-1\) for each neighbor of \(v_i\), and all other entries are zero. Since the number of neighbors is \(\deg(v_i)\), the row sum is \(\deg(v_i)-\deg(v_i)=0\). This holds for every row, including a zero row belonging to an isolated vertex. \(\square\)

Principal Cofactors

For a square matrix, deleting row \(i\) and column \(j\) leaves a smaller square matrix. The signed determinant of that matrix, multiplied by \((-1)^{i+j}\), is the \((i,j)\)-cofactor. We focus on the diagonal case: because \((-1)^{i+i}=1\), its sign factor is positive.

The deleted row and column must correspond to the same vertex. The resulting determinant depends on the entries left in the matrix; it is not the determinant of the original Laplacian with one entry removed. For a graph with one vertex, we use the standard convention that the determinant of the \(0\)-by-\(0\) matrix is \(1\). A graph with no vertices has no vertex at which to take a principal cofactor.

Why the Principal Cofactors Agree

For connected graphs, every principal cofactor has the same value. The key fact is that the only vectors sent to zero by the Laplacian are constant vectors. We establish this using a quadratic-form identity. For a column vector \(x\) with entries \(x_v\), the identity is

Indeed, the diagonal part contributes \(\sum_v\deg(v)x_v^2\). The adjacency part contributes \(2\sum_{uv\in E(G)}x_u x_v\), since each undirected edge appears in both symmetric positions of \(\mathbf{A}(G)\). Subtracting gives the displayed sum: each \(x_v^2\) occurs once for every edge incident with \(v\).

Proof. First suppose \(G\) is connected. If \(\mathbf{L}(G)x=\mathbf{0}\), then \(x^{\mathsf T}\mathbf{L}(G)x=0\). By the quadratic-form identity, this is a sum of nonnegative squares, so \(x_u=x_v\) for every edge \(uv\). Along paths, these equalities imply that all entries of \(x\) are equal. Conversely, every constant vector is in the kernel because the row sums are zero. Thus the kernel has dimension \(1\), and \(\mathbf{L}(G)\) has rank \(n-1\).

Write \(\operatorname{adj}(\mathbf{L})\) for the adjugate matrix, whose \(i,j\) entry is the \((j,i)\)-cofactor. Laplace expansion of determinants gives \(\mathbf{L}\operatorname{adj}(\mathbf{L})=\det(\mathbf{L})\mathbf{I}\): diagonal entries of this product are determinant expansions, while off-diagonal entries are expansions of determinants with a repeated row and are zero. The determinant of \(\mathbf{L}\) is zero because its rows sum to zero. Hence every column of \(\operatorname{adj}(\mathbf{L})\) lies in the one-dimensional kernel spanned by \(\mathbf{1}\). The rank \(n-1\) also means some minor of order \(n-1\) is nonzero, so the adjugate is not zero. Its columns being constant vectors means \(\operatorname{adj}(\mathbf{L})=\mathbf{1}a^{\mathsf T}\) for some nonzero vector \(a\). The adjugate is symmetric because \(\mathbf{L}\) is symmetric and transposing a deleted-row-and-column minor transposes its determinant without changing its value. Therefore \(a_j=a_i\) for all \(i,j\), and all entries of the adjugate are equal. Its diagonal entries are the principal cofactors, so those cofactors are equal.

Now suppose \(G\) is disconnected, with \(c\ge2\) connected components. The same quadratic-form identity shows that a vector is in the kernel exactly when it is constant on each component: equality across every edge forces constancy within a component, and no condition links different components. The kernel therefore has dimension \(c\), so the rank is \(n-c\le n-2\). Every minor of order \(n-1\) is then zero, including each principal cofactor. \(\square\)

For a single-vertex connected graph, the stated empty-determinant convention gives its sole principal cofactor as \(1\). The theorem’s equality claim therefore also holds in that case. The disconnected conclusion concerns graphs with at least one vertex, as required for a principal cofactor to exist.

Common Pitfall and Use

Common mistake: putting the wrong number on the diagonal. In the triangle-with-a-pendant example, vertex \(1\) has two neighbors, vertices \(2\) and \(3\). Its Laplacian row is therefore \((2,-1,-1,0)\). If the diagonal entry is incorrectly written as \(1\), the row becomes \((1,-1,-1,0)\), whose sum is \(1-1-1=-1\), not zero. The correction is to count all neighbors for the diagonal degree, then put \(-1\) in the positions of those neighbors.

Zero row sums are a fast diagnostic when constructing a Laplacian, but they do not by themselves certify every entry: two errors in a row could cancel. Check the diagonal against the degree and each off-diagonal entry against the edge set. When computing a principal cofactor, remove the row and column for the same vertex, and expand the resulting determinant carefully. For a connected graph, the theorem supplies a useful check: repeating the calculation at another vertex must give the same value. For a disconnected graph, each such determinant must be zero. These facts make Laplacian cofactors a structured determinant calculation, rather than an arbitrary one.