tutte_strategy_solves_stochastic_mst
For any graph G, every Tutte strategy T for G solves the adaptive MST identification problem for G.
Statement
theorem tutte_strategy_solves_stochastic_mst {V : Type*} [DecidableEq V] (G : SimpleGraph V) (T : StochasticMstStrategy (Sym2 V)) (hT : stochastic_mst_is_tutte G T) : stochastic_mst_solves G T
- Formalizes
- arXiv:2610.40844 Lemma 3.3
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- stochastic_mst_is_tutteA strategy T is a Tutte strategy for G if it satisfies the Tutte strategy predicate starting from the empty state of contracted and…
- 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…
- StochasticMstStrategyAn adaptive strategy for binary stochastic MST identification is a binary decision tree on a type of edges: either a leaf (no further…
- stochastic_mst_is_tutte_auxFrom state (Z, D) of contracted edges Z and deleted edges D, a strategy is a Tutte strategy for G if at a leaf no edge of G is…
- 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…
Read back from the Lean
For any type V with decidable equality, any simple graph G on V, and any strategy tree T : StochasticMstStrategy (Sym2 V):
if T satisfies stochastic_mst_is_tutte G T, then T satisfies stochastic_mst_solves G T.
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 theorem establishes that any Tutte strategy solves the adaptive minimum spanning tree (MST) identification problem on a graph G. The proof proceeds by structural induction on the strategy tree T in a generalized auxiliary lemma that tracks the sets of confirmed zero-weight edges Z and deleted non-zero edges D. In the leaf case, both definitions impose the identical stopping condition that no edge remains query-eligible. In the query case, any edge eligible under the Tutte condition is an unqueried edge of the graph, and the inductive hypotheses on the two subtrees complete the step. The main theorem then follows by specializing the auxiliary lemma to initially empty sets Z = ∅ and D = ∅.
We set up structural induction on the strategy tree T.
To prove the auxiliary lemma for arbitrary edge sets Z and D, we introduce the strategy tree T and proceed by structural induction on T, yielding a base case for leaves and an inductive case for query nodes.
intro T induction T with
A leaf of a Tutte strategy solves the adaptive MST problem from state (Z, D).
For a leaf node, we introduce the edge sets Z, D and the hypothesis h that the strategy is Tutte. Unfolding the definition of stochastic_mst_solves_aux with stochastic_mst_solves_aux.eq_def shows that a leaf solves the problem precisely when no edge in G is query-eligible, which is identical to the assumption h given by the leaf case of stochastic_mst_is_tutte_aux.
uses
stochastic_mst_solves_aux.eq_def| leaf => intro Z D h rw [stochastic_mst_solves_aux.eq_def] exact hA query node of a Tutte strategy solves the adaptive MST problem if its subtrees do.
For a query node on edge e with child strategies s0 and s1, we introduce Z, D and the Tutte hypothesis h. Unfolding stochastic_mst_is_tutte_aux in h via stochastic_mst_is_tutte_aux.eq_def gives that e is query-eligible, that s0 is Tutte under (Z ∪ {e}, D), and that s1 is Tutte under (Z, D ∪ {e}). Unfolding stochastic_mst_solves_aux in the goal via stochastic_mst_solves_aux.eq_def requires showing that e ∈ E(G), e ∉ Z, e ∉ D, and that s0 and s1 solve the problem on the respective updated states. The query-eligibility of e directly contains the three edge membership conditions, while the induction hypotheses ih0 and ih1 applied to the child Tutte hypotheses establish the two recursive solving obligations.
uses
stochastic_mst_is_tutte_aux.eq_def,stochastic_mst_solves_aux.eq_def| query e s0 s1 ih0 ih1 => intro Z D h rw [stochastic_mst_is_tutte_aux.eq_def] at h rw [stochastic_mst_solves_aux.eq_def] exact ⟨h.1.1, h.1.2.1, h.1.2.2.1, ih0 (insert e Z) D h.2.1, ih1 Z (insert e D) h.2.2⟩Every Tutte strategy for G solves the adaptive MST identification problem for G.
The main theorem follows immediately by applying the auxiliary result tutte_strategy_solves_stochastic_mst_aux with empty initial sets Z = ∅ and D = ∅, which matches the base definitions stochastic_mst_is_tutte and stochastic_mst_solves.
uses
tutte_strategy_solves_stochastic_mst_aux/-- Lemma 3.3: Every Tutte strategy for G solves the adaptive MST identification problem for G. -/ theorem tutte_strategy_solves_stochastic_mst {V : Type*} [DecidableEq V] (G : SimpleGraph V) (T : StochasticMstStrategy (Sym2 V)) (hT : stochastic_mst_is_tutte G T) : stochastic_mst_solves G T := by exact tutte_strategy_solves_stochastic_mst_aux G T ∅ ∅ hT
stochastic_mst_is_tutte_aux.eq_def- Characterizes a Tutte strategy from state (Z, D): a leaf is Tutte if no edge is query-eligible, while a query node on edge e is Tutte if e is query-eligible and both child branches are Tutte strategies under Z ∪ {e} and D ∪ {e} respectively.
stochastic_mst_solves_aux.eq_def- Characterizes when a strategy solves the adaptive MST problem from state (Z, D): a leaf solves it if no edge is query-eligible, while a query node on edge e solves it if e ∈ E(G), e ∉ Z, e ∉ D, and both child branches solve the problem recursively under Z ∪ {e} and D ∪ {e} respectively.
tutte_strategy_solves_stochastic_mst_aux- States that for any graph G and intermediate state (Z, D), every Tutte strategy for G solves the adaptive MST identification problem from state (Z, 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.
/-- From any state (Z, D), a Tutte strategy for G solves the adaptive MST identification problem. -/theorem tutte_strategy_solves_stochastic_mst_aux {V : Type*} [DecidableEq V] (G : SimpleGraph V) : ∀ (T : StochasticMstStrategy (Sym2 V)) (Z D : Finset (Sym2 V)), stochastic_mst_is_tutte_aux G Z D T → stochastic_mst_solves_aux G Z D T := by intro T induction T with | leaf => intro Z D h rw [stochastic_mst_solves_aux.eq_def] exact h | query e s0 s1 ih0 ih1 => intro Z D h rw [stochastic_mst_is_tutte_aux.eq_def] at h rw [stochastic_mst_solves_aux.eq_def] exact ⟨h.1.1, h.1.2.1, h.1.2.2.1, ih0 (insert e Z) D h.2.1, ih1 Z (insert e D) h.2.2⟩/-- Lemma 3.3: Every Tutte strategy for G solves the adaptive MST identification problem for G. -/theorem tutte_strategy_solves_stochastic_mst {V : Type*} [DecidableEq V] (G : SimpleGraph V) (T : StochasticMstStrategy (Sym2 V)) (hT : stochastic_mst_is_tutte G T) : stochastic_mst_solves G T := by exact tutte_strategy_solves_stochastic_mst_aux G T ∅ ∅ hT