AFTD Auto-Formalizing Theoretical Domains

is_mst_for

def

A simple graph T on a finite vertex type V is a minimum spanning tree of G under edge realization α : G.edgeSet → Bool if T is a subgraph of G (T ≤ G), T is a tree (T.IsTree), and for every other spanning tree T' of G (T' ≤ G with T'.IsTree), the number of edges e of G in T with α(e) = true is at most the number of edges e of G in T' with α(e) = true.

Statement

open scoped Classical in
def is_mst_for {V : Type*} [Fintype V] (G T : SimpleGraph V) (α : G.edgeSet → Bool) : Prop
Defined in
scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:260
Verified
06 Nov 2026
Axioms
none listed
Used by 4
  • mst_certificate_monotoneIf a partial realization β is an MST identification certificate for G (is_mst_certificate G β), and β is extended by γ…
  • is_mst_certificateA partial realization β : G.edgeSet → Option Bool is an MST identification certificate for G if there exists a spanning tree T of G (T ≤ G…
  • mst_id_certificate_imp_minor_edges_loop_or_bridgeIf a partial realization β is an MST identification certificate for a connected simple graph G on a finite vertex set, then every…
  • tree_submodular_goal_value_zeroFor every finite simple graph G on a vertex type V that is a tree (G.IsTree), the submodular goal value…

Read back from the Lean

Given a finite type V, simple graphs G and T on V, and a boolean edge-weight/label function α : G.edgeSet → Bool, is_mst_for G T α asserts that: 1. T is a subgraph of G (T ≤ G); 2. T is a tree (T.IsTree, i.e., connected and acyclic, spanning all vertices of V); and 3. For every subgraph T' ≤ G, if T' is a tree, then the number of edges e ∈ G.edgeSet that belong to T and satisfy α e = true is less than or equal to the number of edges e ∈ G.edgeSet that belong to T' and satisfy α e = true.

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

open scoped Classical in
/-- A subgraph is an MST under realization α if it is a spanning tree of minimal weight. -/
def is_mst_for {V : Type*} [Fintype V] (G T : SimpleGraph V) (α : G.edgeSet → Bool) : Prop := T ≤ G ∧ T.IsTree ∧ ∀ T' ≤ G, T'.IsTree →
    (∑ e : G.edgeSet, if (e : Sym2 V) ∈ T.edgeSet then (if α e then 1 else 0) else 0) ≤
    (∑ e : G.edgeSet, if (e : Sym2 V) ∈ T'.edgeSet then (if α e then 1 else 0) else 0)
See it in the graphDiscuss this resultChallenge it