Symmetry And Cofactor Methods On Small Graphs

Why Symmetry Helps with Cofactors

The Matrix-Tree Theorem converts a spanning-tree count into a determinant: for a connected graph, delete one row and the corresponding column from its Laplacian, then take the determinant. Even when that determinant is small enough to calculate directly, repeated patterns in the graph can make the calculation shorter. The same patterns can also organize a separate enumeration of spanning trees, giving a useful check on the result.

Throughout, graphs are finite and simple. A spanning tree of \(G\) is a subgraph containing every vertex of \(G\) that is connected and has no cycles. We write \(t(G)\) for the number of spanning trees. For a graph with at least one vertex, its Laplacian is \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), where \(\mathbf{D}\) has vertex degrees on its diagonal and \(\mathbf{A}\) is the adjacency matrix. A reduced Laplacian is obtained by deleting the row and column belonging to the same chosen vertex. The Matrix-Tree Theorem, established in the earlier material on Laplacians and spanning trees, says that every reduced Laplacian of a connected graph has determinant \(t(G)\).

Definition: An automorphism of \(G\) is a bijection \(\varphi:V(G)\to V(G)\) such that \(uv\in E(G)\) exactly when \(\varphi(u)\varphi(v)\in E(G)\). A graph is symmetric, for the purposes here, when it has automorphisms that permute vertices or edges while preserving adjacency.

An automorphism makes certain rows and columns of a Laplacian interchangeable. Rather than expanding a determinant in its original coordinates, we can sometimes use vectors that are symmetric or antisymmetric under those interchanges. This is a change of basis, not a change in the determinant: if a matrix preserves complementary subspaces, its determinant is the product of the determinants of its restrictions to those subspaces.

Lemma (symmetry-adapted determinant): Let \(M\) be a real symmetric matrix and let \(U\) be a subspace such that \(M(U)\subseteq U\). Then the orthogonal complement \(U^\perp\) is also preserved by \(M\), and \(\det M\) is the product of the determinants of the restrictions of \(M\) to \(U\) and \(U^\perp\).

Proof. Take \(x\in U^\perp\) and \(u\in U\). Since \(M\) is symmetric, \(\langle Mx,u\rangle=\langle x,Mu\rangle\). The hypothesis gives \(Mu\in U\), so \(\langle x,Mu\rangle=0\). Thus \(Mx\in U^\perp\). Choose an orthonormal basis of \(U\), followed by an orthonormal basis of \(U^\perp\). In this combined basis, \(M\) is block diagonal because it preserves both subspaces. The determinant of a block-diagonal matrix is the product of the determinants of its blocks. A change of orthonormal basis does not change the determinant, so the claimed factorization holds. \(\square\)

For a reduced Laplacian, the relevant symmetry must preserve the deleted vertex, so that it also permutes the remaining coordinates. A second useful fact is that an automorphism taking one possible root to another makes the corresponding cofactors equal.

Proposition: If an automorphism of \(G\) takes vertex \(r\) to vertex \(s\), then the reduced Laplacians obtained by deleting \(r\) and \(s\) have equal determinants.

Proof. An automorphism preserves degrees and adjacency, so its permutation of the vertices simultaneously permutes the rows and columns of \(\mathbf{L}\) without changing its entries. After deleting the row and column for \(r\), the remaining coordinates are permuted to the coordinates remaining after deleting \(s\). The two reduced matrices therefore differ only by the same coordinate permutation of rows and columns. A row permutation changes a determinant by the sign of the permutation, and the matching column permutation changes it by the same sign. Their product is \(1\), so the determinants are equal. \(\square\)

A Symmetric Diamond

Worked Example: The Diamond Graph

Let \(G\) have \(V(G)=\{a,b,c,d\}\) and \(E(G)=\{ab,ac,ad,bc,bd\}\). This is \(K_4\) with the edge \(cd\) omitted. The symmetry interchanging \(c\) and \(d\) fixes \(a\) and \(b\). Delete the row and column for \(a\). In the order \(b,c,d\), the reduced Laplacian is

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

The vector \((0,1,-1)\) is antisymmetric under the interchange of \(c,d\), and \(M(0,1,-1)=2(0,1,-1)\). The symmetric vectors have the form \((x,y,y)\). Applying \(M\) gives \((3x-2y,-x+2y,-x+2y)\), so the restriction to symmetric vectors is represented in coordinates \((x,y)\) by \(\begin{pmatrix}3&-2\\-1&2\end{pmatrix}\). Its determinant is \(3\cdot2-(-2)(-1)=6-2=4\). The antisymmetric block contributes \(2\), so

t(G)=\det M=2\cdot4=8.

Independent check by enumeration: A spanning tree has three edges. There are \(\binom{5}{3}=10\) three-edge subsets of \(E(G)\). The only cycles in this graph are the triangles with edge sets \(\{ab,ac,bc\}\) and \(\{ab,ad,bd\}\). These two subsets are not trees. Every other three-edge subset is connected and acyclic: with four vertices and three edges, a disconnected subset would have to leave at least one vertex isolated and place all three edges on the other three vertices, which would form one of the two listed triangles. Thus \(10-2=8\) subsets are spanning trees, agreeing with the cofactor.

A Wheel: Symmetry in a Four-by-Four Cofactor

Worked Example: The Wheel with Four Rim Vertices

Let \(G\) have \(V(G)=\{h,1,2,3,4\}\) and \(E(G)=\{h1,h2,h3,h4,12,23,34,41\}\). Delete the row and column for the hub \(h\). Each rim vertex has degree \(3\), and the reduced Laplacian is

M= \begin{pmatrix} 3&-1&0&-1\\ -1&3&-1&0\\ 0&-1&3&-1\\ -1&0&-1&3 \end{pmatrix}.

The following four vectors are linearly independent, so they form a basis. Direct multiplication gives eigenvalues \(1,3,3,5\), respectively:

\begin{array}{c|c} \text{vector}&\text{eigenvalue}\\ (1,1,1,1)&1\\ (1,0,-1,0)&3\\ (0,1,0,-1)&3\\ (1,-1,1,-1)&5 \end{array}

For example, the first row of \(M(1,1,1,1)\) is \(3-1-1=1\), and the first row of \(M(1,0,-1,0)\) is \(3+0=3\); the other coordinates give the same respective multiples. Therefore \(\det M=1\cdot3\cdot3\cdot5=45\), and \(t(G)=45\).

Independent check by symmetry-based enumeration: A spanning tree uses four edges. Let \(k\) be the number of spokes \(hi\) it uses, so it uses \(4-k\) rim edges. The selected rim edges must form a forest, and each of their connected components must contain exactly one selected spoke. If a component contained no spoke, the whole selected graph would be disconnected; if it contained two, the rim path between them and the two spokes would form a cycle.

For \(k=1\), the rim edges form a path of three edges, obtained by omitting one of the four rim edges. There are \(4\) choices for the omitted edge and \(4\) choices for the single spoke, giving \(4\cdot4=16\). For \(k=2\), omit two rim edges. If the omitted edges are adjacent, there are \(4\) choices and the remaining rim components have sizes \(3\) and \(1\); there are \(3\cdot1=3\) choices of one spoke in each. This gives \(4\cdot3=12\). If the omitted edges are opposite, there are \(2\) choices, the components have sizes \(2\) and \(2\), and there are \(2\cdot2=4\) spoke choices, giving \(2\cdot4=8\). Thus the \(k=2\) case contributes \(12+8=20\).

For \(k=3\), one rim edge remains. There are \(4\) choices for it; its components have sizes \(2,1,1\), so there are \(2\) choices of one spoke in each component. This gives \(4\cdot2=8\). For \(k=4\), no rim edges remain and all four spokes must be selected, giving \(1\) tree. The case \(k=0\) leaves the hub disconnected. The total is \(16+20+8+1=45\), agreeing with the determinant.

A Triangular Prism: Two Symmetry Blocks

Worked Example: The Triangular Prism

Let \(G\) have \(V(G)=\{a,b,c,A,B,C\}\) and \(E(G)=\{ab,bc,ca,AB,BC,CA,aA,bB,cC\}\). The lowercase and uppercase vertices each form a triangle, and the three remaining edges join corresponding vertices. Delete \(c\). In the order \(a,b,A,B,C\), the reduced Laplacian is

M= \begin{pmatrix} 3&-1&-1&0&0\\ -1&3&0&-1&0\\ -1&0&3&-1&-1\\ 0&-1&-1&3&-1\\ 0&0&-1&-1&3 \end{pmatrix}.

The automorphism exchanging \(a,b\) and \(A,B\), while fixing \(C\), preserves this matrix. First consider vectors \((x,-x,y,-y,0)\). Multiplication by \(M\) gives coordinates \((4x-y,-4x+y,4y-x,-4y+x,0)\), so this two-dimensional subspace has matrix \(\begin{pmatrix}4&-1\\-1&4\end{pmatrix}\) and determinant \(16-1=15\). On the symmetric subspace of vectors \((x,x,y,y,z)\), the output has coordinates \((2x-y,2x-y,-x+2y-z,-x+2y-z,-2y+3z)\). Its restriction is represented by

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

The determinant of this block is \(2(2\cdot3-(-1)(-2))-(-1)((-1)\cdot3-(-1)\cdot0)=2(6-2)-3=8-3=5\). The two invariant subspaces together have dimensions \(2+3=5\), so they account for the entire reduced matrix. Hence \(t(G)=\det M=15\cdot5=75\).

Independent check by counting according to the number of joining edges: Let \(k\) be the number of edges among \(aA,bB,cC\) used in a spanning tree. There are six vertices, so a tree has five edges. With \(k=1\), each triangle must contribute two edges to connect all its vertices. Each triangle has \(3\) choices of a two-edge path, and there are \(3\) choices of the joining edge: \(3\cdot3\cdot3=27\).

With \(k=2\), the triangles contribute one and two edges, in either order. Choose the triangle with one edge in \(2\) ways, choose that edge in \(3\) ways, and choose a spanning path in the other triangle in \(3\) ways. In the triangle with one edge, its vertices split into a pair and a singleton. The two joining edges must use one vertex from each component, giving \(2\) choices. The count is \(2\cdot3\cdot3\cdot2=36\).

With \(k=3\), the triangles contribute either zero and two edges, in either order, or one edge each. The first two possibilities give \(2\cdot3=6\) choices. For one edge in each triangle there are \(3\cdot3=9\) choices, but \(3\) choices use the same pair of corresponding positions in both triangles; those choices form a four-cycle together with two joining edges and leave the third corresponding pair separate. The other \(9-3=6\) choices are trees. Thus the \(k=3\) contribution is \(6+6=12\). No tree can have \(k=0\), since that leaves the two triangles disconnected. The total \(27+36+12=75\) confirms the cofactor.

Common Pitfall and Practical Method

Do not take the determinant of the full Laplacian as the tree count. For the diamond in the first example, the full Laplacian has every row summing to zero, so \(\mathbf{L}(1,1,1,1)^{\mathsf T}=0\) and \(\det\mathbf{L}=0\). The incorrect calculation “\(t(G)=\det\mathbf{L}=0\)” contradicts the eight spanning trees. The correction is to delete the same row and column before taking the determinant: the reduced determinant is \(8\). For a connected graph, the full Laplacian is singular precisely because its rows sum to zero; the Matrix-Tree Theorem concerns a cofactor, not the full determinant.

When using symmetry, check that the symmetry really preserves the chosen reduced matrix. An automorphism that moves the deleted vertex need not act as a coordinate permutation on that one reduced matrix, although the proposition shows that the corresponding root cofactors agree. Then identify invariant subspaces, calculate the smaller restrictions, and multiply their determinants. Finally, check the result independently where feasible: organize spanning trees by a symmetric feature such as the number of spokes or joining edges, and verify that every possible case is included exactly once.

Check Your Understanding

Use the cofactor and symmetry ideas from the examples. When enumerating, specify what structural feature separates your cases.

For the diamond graph, why does the vector \((0,1,-1)\) belong to the antisymmetric subspace, and what eigenvalue does the reduced Laplacian assign to it?
In the wheel example, explain why selecting no spokes cannot give a spanning tree.
For the triangular prism, why are the three choices using the same pair of positions in both triangles excluded from the one-edge-per-triangle case?
Explain why the full Laplacian determinant cannot count spanning trees of a connected graph with at least one vertex.
Suppose a graph automorphism fixes a chosen root. What does it do to the coordinates of the corresponding reduced Laplacian?