Kirchhoff's matrix-tree theorem
ProvedClassicalGaps.kirchhoff_matrix_treedeterminantsgraph-theorymatrix-tree-theoremspanning-trees
For a connected finite simple graph , the determinant of the Laplacian matrix of with any one row and column deleted equals the number of spanning trees of ; a spanning tree is an edge subset with edges whose induced spanning subgraph is connected.
Preamble
import Mathlib.Combinatorics.SimpleGraph.LapMatrix import Mathlib.Combinatorics.SimpleGraph.Connectivity.Connected import Mathlib.Combinatorics.SimpleGraph.Finite open Classical
Formal statement
theorem ClassicalGaps.kirchhoff_matrix_tree {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (v₀ : V) :
((G.lapMatrix ℝ).submatrix (fun x : {x : V // x ≠ v₀} => x.1)
(fun x : {x : V // x ≠ v₀} => x.1)).det =
((Finset.univ.filter (fun F : Finset (Sym2 V) =>
F ⊆ G.edgeFinset ∧ (SimpleGraph.fromEdgeSet (↑F : Set (Sym2 V))).Connected ∧
F.card + 1 = Fintype.card V)).card : ℝ) := by sorrySource
G. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird, Ann. Phys. 72 (1847); see https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem