is_mst_certificate
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
- mst_certificate_monotoneIf a partial realization β is an MST identification certificate for G (is_mst_certificate G β), and β is extended by γ…
- nonadaptive_mst_stopping_time_of_isTreeIf G is a tree, then under any binary edge realization α and any querying order π, the stopping time is 0 because the unique spanning tree…
- is_submodular_goal_functionA function g : (G.edgeSet → Option Bool) → ℕ is a submodular goal function with goal value Q for G if: g evaluates to 0 on the empty…
- 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…
- nonadaptive_mst_stopping_timeGiven a simple graph G, a querying order π : List G.edgeSet, and a realization α : G.edgeSet → Bool, the stopping time is the minimum…
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 α