stochastic_mst_query_continuation_solves
For a graph G and an edge e that is query-eligible at the initial state (∅, ∅), the strategy querying e with children s₀ and s₁ solves the adaptive MST identification problem for G if and only if s₀ solves the subproblem from state ({e}, ∅) and s₁ solves the subproblem from state (∅, {e}).
Statement
theorem stochastic_mst_query_continuation_solves {V : Type*} [DecidableEq V] (G : SimpleGraph V) (e : Sym2 V) (s₀ s₁ : StochasticMstStrategy (Sym2 V)) (he : stochastic_mst_query_eligible G ∅ ∅ e) : stochastic_mst_solves G (StochasticMstStrategy.query e s₀ s₁) ↔ stochastic_mst_solves_aux G {e} ∅ s₀ ∧ stochastic_mst_solves_aux G ∅ {e} s₁
- Formalizes
- arXiv:2610.40844 Lemma 3.1
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- stochastic_mst_solvesA strategy T solves the adaptive MST identification problem for G if it solves the problem starting from the empty state of contracted and…
- stochastic_mst_solves_auxFrom state (Z, D) of contracted edges Z and deleted edges D, a strategy solves the adaptive MST identification problem for G if at every…
- stochastic_mst_query_eligibleFor a simple graph G on a vertex type V, finite sets Z and D of edges (Finsets of Sym2 V: Z the edges queried with weight 0, which are…
- StochasticMstStrategyAn adaptive strategy for binary stochastic MST identification is a binary decision tree on a type of edges: either a leaf (no further…
Read back from the Lean
For any type V with decidable equality, any simple graph G on V, any edge/pair e : Sym2 V, and any strategies s₀, s₁ : StochasticMstStrategy (Sym2 V), assuming e is query-eligible in G with respect to empty sets Z = ∅ and D = ∅ (stochastic_mst_query_eligible G ∅ ∅ e), the query strategy StochasticMstStrategy.query e s₀ s₁ solves G (stochastic_mst_solves G (query e s₀ s₁)) if and only if s₀ solves the auxiliary problem with edge sets {e} and ∅ (stochastic_mst_solves_aux G {e} ∅ s₀) and s₁ solves the auxiliary problem with edge sets ∅ and {e} (stochastic_mst_solves_aux G ∅ {e} s₁).
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 proof unfolds the definition of solving the stochastic MST problem into the auxiliary problem at the initial state with empty contracted and deleted sets, then expands the query constructor using its definitional equation. The eligibility hypothesis provides that the queried edge belongs to the graph, while the non-membership conditions in the empty set hold vacuously and singleton insertions simplify, reducing the equivalence to an identity.
The goal is rewritten so that the query strategy solving the problem from the initial empty state (∅, ∅) is expressed in terms of edge membership and the subproblems on the branch continuations.
Unfolding the definition of stochastic_mst_solves expresses solving the overall problem as solving the auxiliary problem stochastic_mst_solves_aux starting from empty contracted and deleted edge sets (∅, ∅). Rewriting with stochastic_mst_solves_aux.eq_2 then expands the query node into the conjunction requiring e ∈ G.edgeSet, e ∉ ∅, e ∉ ∅, that s₀ solves the auxiliary problem with e added to the contracted edges, and that s₁ solves the auxiliary problem with e added to the deleted edges.
uses
stochastic_mst_solves,stochastic_mst_solves_aux.eq_2rw [stochastic_mst_solves, stochastic_mst_solves_aux.eq_2]The conditions e ∈ G.edgeSet and e ∉ ∅ are discharged, and inserting e into ∅ simplifies to {e}, proving the equivalence.
The first condition of the hypothesis he (that e is query-eligible at (∅, ∅)) guarantees e ∈ G.edgeSet. The non-membership conditions e ∉ ∅ hold vacuously for the empty set, and inserting e into the empty set simplifies to the singleton set {e}. Simplification with these facts leaves identical conjunctions on both sides of the equivalence, completing the proof.
simp [he.1]
stochastic_mst_solves- A strategy solves the stochastic MST identification problem on a graph G if and only if it solves the auxiliary problem starting with empty sets of contracted and deleted edges (Z = ∅ and D = ∅).
stochastic_mst_solves_aux.eq_2- A query strategy on edge e with continuation branches s₀ and s₁ solves the auxiliary problem from state (Z, D) if and only if e is an edge of G, e ∉ Z, e ∉ D, s₀ solves the subproblem from state (insert e Z, D), and s₁ solves the subproblem from state (Z, insert e D).
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.
/-- Lemma 3.1: Querying an eligible edge e and following s₀ on 0 and s₁ on 1 solves MST-ID iff s₀ and s₁ solve the contracted and deleted subproblems. -/theorem stochastic_mst_query_continuation_solves {V : Type*} [DecidableEq V] (G : SimpleGraph V) (e : Sym2 V) (s₀ s₁ : StochasticMstStrategy (Sym2 V)) (he : stochastic_mst_query_eligible G ∅ ∅ e) : stochastic_mst_solves G (StochasticMstStrategy.query e s₀ s₁) ↔ stochastic_mst_solves_aux G {e} ∅ s₀ ∧ stochastic_mst_solves_aux G ∅ {e} s₁ := by rw [stochastic_mst_solves, stochastic_mst_solves_aux.eq_2] simp [he.1]