A reduced incidence submatrix has determinant ±1 on a spanning tree and 0 otherwise
ProvedClassicalGaps.orientedIncMatrix_submatrix_det_eq_spanningTree_indicatorLet be a finite simple graph on vertex set with oriented incidence matrix (ClassicalGaps.orientedIncMatrix), fix a base vertex , let be a set of edges of , and fix any bijection between and . Form the square matrix indexed by (deleting the row for and reindexing the columns from through ). Then is if the edges in form a spanning tree of (the subgraph they induce is connected), and otherwise. Squaring makes the statement independent of the choice of and of sign conventions.
This is the key combinatorial fact in Kirchhoff's matrix-tree theorem: combined with the Cauchy-Binet formula (ClassicalGaps.cauchy_binet_det) applied to ClassicalGaps.lapMatrix_eq_orientedIncMatrix_mul_transpose, it turns the sum of squared minors into exactly the count of spanning trees. The classical proof is by induction on : if contains a cycle the columns are linearly dependent (determinant ); if is a spanning tree, expanding along a leaf vertex's row gives times the determinant for the smaller tree with that leaf removed.
Formalization Note: child lemma of ClassicalGaps.kirchhoff_matrix_tree.
import Mathlib import Definitions.Def_ClassicalGaps_orientedIncMatrix open Classical Matrix
namespace ClassicalGaps
theorem orientedIncMatrix_submatrix_det_eq_spanningTree_indicator
{V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(v₀ : V) (F : Finset (Sym2 V)) (hF : F ⊆ G.edgeFinset) (hcard : F.card + 1 = Fintype.card V)
(e : {x : V // x ≠ v₀} ≃ {x // x ∈ F}) :
(Matrix.of (fun a b : {x : V // x ≠ v₀} => orientedIncMatrix G a.1 ((e b : Sym2 V)))).det ^ 2 =
(if (SimpleGraph.fromEdgeSet (↑F : Set (Sym2 V))).Connected then (1:ℝ) else 0) := by sorry
end ClassicalGaps