mst_weight
def
The minimum spanning tree weight of a finite edge-weighted simple graph (G, w) is the infimum over all spanning trees T ≤ G of the sum of the weights of the edges of T.
Statement
noncomputable def mst_weight {V : Type*} [Fintype V] (G : SimpleGraph V) (w : Sym2 V → ℝ) : ℝ
- Defined in
- arXiv:2611.14755, Section 2
- Verified
- 15 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a finite type V, a simple graph G on V, and a weight function w : Sym2 V → ℝ on unordered pairs of vertices, mst_weight G w is defined as the infimum in ℝ (sInf) of the set of total weights ∑ e ∈ T.edgeFinset, w e over all spanning subgraphs T : SimpleGraph V such that T ≤ G and T is a tree (T.IsTree, i.e., connected and acyclic).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The weight of a minimum spanning tree in a finite edge-weighted graph (G, w). -/ noncomputable def mst_weight {V : Type*} [Fintype V] (G : SimpleGraph V) (w : Sym2 V → ℝ) : ℝ := open scoped Classical in sInf { ∑ e ∈ T.edgeFinset, w e | (T : SimpleGraph V) (_ : T ≤ G) (_ : T.IsTree) }