AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_is_tutte

def

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

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
See it in the graphDiscuss this resultChallenge it