AFTD Auto-Formalizing Theoretical Domains

is_mst_certificate

def

A partial realization β : G.edgeSet → Option Bool is an MST identification certificate for G if there exists a spanning tree T of G (T ≤ G with T.IsTree) such that for every full realization α : G.edgeSet → Bool extending β (meaning α e = b whenever β e = some b), T is a minimum spanning tree of G under α (is_mst_for G T α).

Statement

open scoped Classical in
def is_mst_certificate {V : Type*} [Fintype V] (G : SimpleGraph V) (β : G.edgeSet → Option Bool) : Prop
Defined in
scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:267
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • is_mst_forA 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…
Used by 6

Read back from the Lean

Given a finite type V, a simple graph G on V, and a partial assignment β : G.edgeSet → Option Bool, is_mst_certificate G β asserts that there exists a subgraph T ≤ G such that: 1. T is a tree (T.IsTree, i.e., connected and acyclic on the vertex set V), and 2. For every total boolean edge assignment α : G.edgeSet → Bool, if α extends β (i.e., for every edge e ∈ G.edgeSet and every boolean b, if β e = some b then α e = b), then T is a minimum spanning tree of G under the edge weights given by α (is_mst_for G T α).

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 partial realization is an MST certificate if some spanning tree is an MST under every full extension. -/
def is_mst_certificate {V : Type*} [Fintype V] (G : SimpleGraph V) (β : G.edgeSet → Option Bool) : Prop := ∃ T ≤ G, T.IsTree ∧ ∀ α : G.edgeSet → Bool, (∀ e b, β e = some b → α e = b) → is_mst_for G T α
See it in the graphDiscuss this resultChallenge it