AFTD Auto-Formalizing Theoretical Domains

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) }
See it in the graphDiscuss this resultChallenge it