nonadaptive_mst_stopping_time_of_isTree
If 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 certified before querying any edges.
Statement
theorem nonadaptive_mst_stopping_time_of_isTree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hT : G.IsTree) (π : List G.edgeSet) (α : G.edgeSet → Bool) : nonadaptive_mst_stopping_time G π α = 0
- Formalizes
- arXiv:2610.40844 Sec. 2
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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…
- 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
For any finite type V with decidable equality, any simple graph G on V, any proof hT that G is a tree (connected and acyclic), any list π of edges of G, and any boolean weight assignment α : G.edgeSet → Bool, the nonadaptive MST stopping time nonadaptive_mst_stopping_time G π α is equal to 0.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The stopping time of the algorithm is defined as the infimum of the number of edge queries needed to certify a minimum spanning tree. To show that this stopping time is 0, it suffices to prove that zero queries already yield an MST certificate. Since the graph is given to be a tree, it has a unique spanning tree—itself—and any observation (in particular, no edge queries at all) guarantees the MST.
It suffices to show that zero edge queries certify a minimum spanning tree for G.
By definition, the nonadaptive stopping time is the infimum of the query counts k at which the queried edges certify an MST. By `Nat.sInf_eq_zero.mpr`, showing this infimum is 0 reduces to showing that either 0 belongs to the set of valid query counts or the set is empty; taking the first alternative leaves the goal of showing that k = 0 queries certify an MST.
uses
Nat.sInf_eq_zero.mprdsimp [nonadaptive_mst_stopping_time] apply Nat.sInf_eq_zero.mpr left
Zero queries certify an MST for G.
Because G is assumed to be a tree (hT), it is its own unique spanning tree. The lemma `tree_submodular_goal_value_zero_is_mst_certificate` establishes that on a tree, any partial observation function β certifies an MST; this immediately applies to the empty observation corresponding to 0 queries.
uses
tree_submodular_goal_value_zero_is_mst_certificateexact tree_submodular_goal_value_zero_is_mst_certificate G hT _
Nat.sInf_eq_zero.mpr- The infimum of a set of natural numbers is 0 if 0 is an element of the set or if the set is empty.
tree_submodular_goal_value_zero_is_mst_certificate- If a graph G is a tree, then any partial edge assignment β is a minimum spanning tree certificate for G.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- On a tree, any edge order stops in 0 queries since the tree itself is already certified as the unique spanning tree. -/theorem nonadaptive_mst_stopping_time_of_isTree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hT : G.IsTree) (π : List G.edgeSet) (α : G.edgeSet → Bool) : nonadaptive_mst_stopping_time G π α = 0 := by dsimp [nonadaptive_mst_stopping_time] apply Nat.sInf_eq_zero.mpr left exact tree_submodular_goal_value_zero_is_mst_certificate G hT _