AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_query_eligible

def

For 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 contracted, D those queried with weight 1, which are deleted) and an edge e (an element of Sym2 V), e is eligible for a query when: e is an edge of G, e is not in Z, e is not in D, and writing e = s(u, v), the vertices u and v are not joined by a path in the graph whose edges are exactly the elements of Z (so e is not a loop of the minor G/Z minus D), but are joined by a path in G after deleting e and the edges of D (so e is not a bridge of that minor).

Statement

def stochastic_mst_query_eligible {V : Type*} (G : SimpleGraph V) (Z D : Finset (Sym2 V))
    (e : Sym2 V) : Prop
Defined in
arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 2.1 and Lemma 2.2: the minor G_beta obtained by contracting 0-edges and deleting 1-edges; an edge is worth querying iff it is neither a loop nor a bridge of G_beta
Verified
06 Nov 2026
Axioms
none listed
Used by 7

Read back from the Lean

For a type V, a simple graph G on V, finite sets of edges/pairs Z, D : Finset (Sym2 V), and an edge/pair e : Sym2 V, stochastic_mst_query_eligible G Z D e asserts that: 1. e is an edge of G (e ∈ G.edgeSet); 2. e is not in Z (e ∉ Z); 3. e is not in D (e ∉ D); and 4. there exist vertices u, v : V such that e = s(u, v) (i.e., u and v are the endpoints of e), - u and v are not reachable from each other in the simple graph with edge set Z (SimpleGraph.fromEdgeSet ↑Z), and - u and v are reachable from each other in the graph obtained from G by deleting the edge e and all edges in D (G.deleteEdges (insert e ↑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

def stochastic_mst_query_eligible {V : Type*} (G : SimpleGraph V) (Z D : Finset (Sym2 V))
    (e : Sym2 V) : Prop :=
  e ∈ G.edgeSet ∧ e ∉ Z ∧ e ∉ D ∧ ∃ u v : V, e = s(u, v) ∧
    ¬ (SimpleGraph.fromEdgeSet (↑Z : Set (Sym2 V))).Reachable u v ∧
    (G.deleteEdges (insert e (↑D : Set (Sym2 V)))).Reachable u v
See it in the graphDiscuss this resultChallenge it