Incidence Matrices And Spanning-Tree Minors

From Edges to a Matrix

An incidence matrix records which vertices meet which edges, with signs supplied by an orientation. The orientation is a bookkeeping choice: it makes the columns signed, but it does not change which edge sets are trees. The key fact is that square minors of this matrix detect forests. When exactly one vertex row is omitted from a connected graph, the corresponding minors identify its spanning trees.

All graphs below are finite and simple. An orientation of a graph chooses, for each edge \(uv\), one endpoint as its tail and the other as its head. The resulting directed edge is not a change to the underlying graph; it is only a choice used to define a matrix.

Rows and columns in a submatrix are taken in fixed orders. Changing those orders can change a determinant's sign, but not whether it is zero or its absolute value. Reversing the orientation of an edge multiplies its column by \(-1\), which likewise changes at most the sign of a determinant using that column. We use the convention that a \(0\)-by-\(0\) determinant equals \(1\).

The Forest-Minor Characterization

For a chosen row set \(R\), write \(U=V\setminus R\) for the omitted vertices. The condition on \(U\) is component-by-component: every component formed by the selected edges must contain exactly one omitted vertex. Components include isolated vertices, so this condition also accounts for vertices incident to no selected edge.

Here a forest is a graph with no cycles; isolated vertices count as components. We prove the determinant fact needed for the theorem first.

Proof. We use induction on the number \(k\) of vertices of \(T\). If \(k=1\), there are no edges and the matrix is \(0\)-by-\(0\), whose determinant is \(1\). Now let \(k\ge2\), and suppose the claim holds for trees with \(k-1\) vertices. A tree with at least two vertices has at least two leaves: for example, the endpoints of a longest path must have degree one, since an additional neighbor would either extend the path or create a cycle. Thus there is a leaf \(x\ne r\). In the matrix with row \(r\) deleted, the row for \(x\) has exactly one nonzero entry, equal to \(1\) or \(-1\), in the column for its sole incident edge \(e\). Expanding the determinant along row \(x\) gives, up to sign, the determinant obtained by deleting row \(x\) and column \(e\). Removing a leaf and its incident edge leaves a tree on \(k-1\) vertices, still with row \(r\) deleted. By the induction hypothesis its determinant is \(1\) or \(-1\). Multiplication by the entry \(1\) or \(-1\), and the cofactor sign, leaves the determinant equal to \(1\) or \(-1\). \(\square\)

Proof of the theorem. First suppose \(\det \mathbf{B}[R,F]\ne0\). If the edges \(F\) contained a cycle, the columns belonging to that cycle would be linearly dependent: traverse the cycle in one direction, assigning coefficient \(1\) to an edge whose orientation agrees with the traversal and \(-1\) to an edge whose orientation disagrees. At every vertex of the cycle the signed contributions cancel, so the resulting nontrivial combination of columns is zero. This dependence remains in the selected rows, contradicting the nonzero determinant. Therefore \((V,F)\) is a forest.

Consider a component \(C\) of \((V,F)\), with \(k\) vertices and \(e_C\) selected edges. Since it is a tree, including when it is an isolated vertex, \(e_C=k-1\). Let \(r_C=|R\cap C|\). The columns for edges in \(C\) have nonzero entries only in rows from \(C\). If \(r_C<e_C\), those \(e_C\) columns are linearly dependent when restricted to the \(r_C\) rows, contradicting invertibility of the square matrix. If \(r_C>e_C\), the \(r_C\) rows from \(C\) have nonzero entries only in the \(e_C\) columns from \(C\), so those rows are linearly dependent, again contradicting invertibility. Hence \(r_C=e_C=k-1\). Exactly \(k-r_C=1\) vertex of \(C\) lies in \(U\).

Conversely, suppose \((V,F)\) is a forest and each component has exactly one vertex in \(U\). A component on \(k\) vertices then has \(k-1\) edges and \(k-1\) selected rows. Permute rows and columns to group them by component. The resulting square matrix is block diagonal, with one square block for each component. For a nontrivial component, its block is the incidence matrix of a tree with the row of its unique omitted vertex deleted, so the lemma gives determinant \(1\) or \(-1\). For an isolated component, its block is \(0\)-by-\(0\), with determinant \(1\). The determinant of the whole matrix is, up to the signs of the row and column permutations, the product of these block determinants. Its absolute value is therefore \(1\), proving both nonvanishing and the claimed magnitude. \(\square\)

The Spanning-Tree Case

Proof. The rows retained are all vertices except \(r\), so there is just one omitted vertex. By the theorem, a nonzero determinant requires \(F\) to be a forest with exactly one omitted vertex in each component. Since the only omitted vertex is \(r\), the forest can have only one component: every component must contain \(r\), which is possible only if there is one component. Thus \((V,F)\) is connected and acyclic, so it is a spanning tree. Conversely, a spanning tree is a forest with one component containing the omitted vertex \(r\), so the theorem gives a determinant of absolute value \(1\). \(\square\)

This statement applies whether or not \(G\) itself is connected. If \(G\) is disconnected, it has no spanning tree, and every such \((n-1)\)-column minor is zero. The case \(n=1\) is included: the empty edge set is the spanning tree on one vertex, and its reduced incidence determinant is the empty determinant \(1\).

Worked Minors

Common Pitfalls and Why the Criterion Matters

Do not ignore cofactor signs. In the triangle example, the second term of the first-row expansion has a minus sign because it comes from column \(2\). The correct calculation is \((-1)(1)-(-1)(1)=-1+1=0\). Dropping that cofactor sign would produce a wrong determinant, even though the graph-theoretic conclusion is known.

A forest alone does not guarantee a nonzero arbitrary minor. The rows must also match the components correctly: each component must have exactly one omitted vertex. The general criterion is more precise than the spanning-tree corollary, which is the special case where there is only one omitted vertex in the entire graph.

The unit determinants are useful because they turn a structural question into a matrix test without introducing complicated values: an edge set gives a nonzero spanning-tree minor exactly when it is a spanning tree, and the nonzero determinant is always \(1\) or \(-1\). The next step in the subject uses incidence matrices to connect these minors with spanning-tree counts; that counting identity requires additional determinant machinery beyond the criterion proved here.