stochastic_mst_is_tutte
A strategy T is a Tutte strategy for G if it satisfies the Tutte strategy predicate starting from the empty state of contracted and deleted edges.
Statement
def stochastic_mst_is_tutte {V : Type*} [DecidableEq V] (G : SimpleGraph V) (T : StochasticMstStrategy (Sym2 V)) : Prop
- Defined in
- arXiv:2610.40844 Section 3
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 2
- 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…
- StochasticMstStrategyAn adaptive strategy for binary stochastic MST identification is a binary decision tree on a type of edges: either a leaf (no further…
- Used by 1
- tutte_strategy_solves_stochastic_mstFor any graph G, every Tutte strategy T for G solves the adaptive MST identification problem for G.
Read back from the Lean
For a type V with decidable equality, a simple graph G on V, and a binary strategy tree T : StochasticMstStrategy (Sym2 V) (whose internal nodes query unordered pairs of vertices in V), stochastic_mst_is_tutte G T defines a property asserting that T is a valid Tutte-type contraction/deletion strategy for G, starting from empty sets of contracted edges Z = ∅ and deleted edges D = ∅.
Specifically, stochastic_mst_is_tutte_aux G Z D T is defined by recursion on the tree T:
1. If T is a leaf (StochasticMstStrategy.leaf): asserts that there is no edge e that is query-eligible with respect to (G, Z, D).
2. If T is an internal node StochasticMstStrategy.query e s₀ s₁: asserts that:
- e is query-eligible with respect to (G, Z, D);
- the left subtree s₀ satisfies the predicate with Z updated to insert e Z and D unchanged;
- the right subtree s₁ satisfies the predicate with Z unchanged and D updated to insert e D.
An edge e : Sym2 V is query-eligible (stochastic_mst_query_eligible G Z D e) if and only if:
- e is an edge of G (e ∈ G.edgeSet);
- e ∉ Z and e ∉ D;
- there exist vertices u, v : V such that e = s(u, v) (i.e., u and v are the endpoints of e) such that:
- u and v are not reachable from each other in the graph on V with edge set Z (meaning adding e to Z does not form a cycle in Z, i.e., e is not a loop);
- u and v are reachable from each other in G after deleting all edges in D ∪ {e} (meaning e is not a bridge in G \ D).
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
/-- A Tutte strategy for graph G is a binary decision tree whose root starts at the empty state (∅, ∅). -/ def stochastic_mst_is_tutte {V : Type*} [DecidableEq V] (G : SimpleGraph V) (T : StochasticMstStrategy (Sym2 V)) : Prop := stochastic_mst_is_tutte_aux G ∅ ∅ T