Incidence minor has determinant zero when the edge set is disconnected
ProvedClassicalGaps.orientedIncMatrix_submatrix_det_eq_zero_of_not_connectedcombinatoricsgraph-theorylinear-algebra
Let be a finite simple graph with oriented incidence matrix (rows indexed by vertices, columns by edges; each edge column has and at its two endpoints). Fix a vertex and a set of edges of with , and let be the square matrix obtained from by deleting the row of and keeping only the columns in .
If the graph on with edge set is not connected, then
This is the "disconnected" half of the key lemma in the standard proof of Kirchhoff's matrix-tree theorem (the determinant of such a minor is when is a spanning tree and otherwise). The reason: some connected component of misses , and the rows of indexed by sum to zero, since every edge of has either both endpoints in (contributing ) or neither.
Preamble
import Mathlib import Definitions.Def_ClassicalGaps_orientedIncMatrix open Classical Matrix
Formal statement
namespace ClassicalGaps
theorem orientedIncMatrix_submatrix_det_eq_zero_of_not_connected
{V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(v₀ : V) (F : Finset (Sym2 V)) (hF : F ⊆ G.edgeFinset)
(e : {x : V // x ≠ v₀} ≃ {x // x ∈ F})
(hnc : ¬ (SimpleGraph.fromEdgeSet (↑F : Set (Sym2 V))).Connected) :
(Matrix.of (fun a b : {x : V // x ≠ v₀} => orientedIncMatrix G a.1 ((e b : Sym2 V)))).det = 0 := by sorry
end ClassicalGapsSource
Standard proof of Kirchhoff's matrix-tree theorem; see e.g. Bollobás, Modern Graph Theory, Section II.3 (Theorem 12 and its proof). Child lemma of ClassicalGaps.orientedIncMatrix_submatrix_det_eq_spanningTree_indicator.