AFTD Auto-Formalizing Theoretical Domains

minor_edge_is_loop

def

For a simple graph G and a partial edge-weight realization β : G.edgeSet → Option Bool, an edge e of G is a loop in the minor G_β (obtained by contracting edges with weight 0 and deleting edges with weight 1) if its endpoints are connected by a path in the subgraph of contracted edges (weight 0).

Statement

open scoped Classical in
def minor_edge_is_loop {V : Type*} (G : SimpleGraph V) (β : G.edgeSet → Option Bool)
    (e : G.edgeSet) : Prop
Defined in
arXiv:2610.40844 Section 2.1
Verified
07 Nov 2026
Axioms
none listed
Used by 2

Read back from the Lean

Given a type V, a simple graph G on V, an edge-labeling function β : G.edgeSet → Option Bool, and an edge e : G.edgeSet, the definition minor_edge_is_loop G β e asserts that there exist vertices u, v : V such that: 1. (e : Sym2 V) = s(u, v) (i.e., u and v are the endpoints of e), and 2. u and v are reachable from each other in the simple graph on V whose edges are those edges s of G for which β ⟨s, h⟩ = some false (specifically, the graph SimpleGraph.fromEdgeSet {s | ∃ h : s ∈ G.edgeSet, β ⟨s, h⟩ = some false}).

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

open scoped Classical in
/-- An edge of G is a loop in the minor G_β if its endpoints are connected by edges with weight 0 (contracted edges). -/
def minor_edge_is_loop {V : Type*} (G : SimpleGraph V) (β : G.edgeSet → Option Bool)
    (e : G.edgeSet) : Prop := ∃ u v : V, (e : Sym2 V) = s(u, v) ∧
    (SimpleGraph.fromEdgeSet {s | ∃ h : s ∈ G.edgeSet, β ⟨s, h⟩ = some false}).Reachable u v
See it in the graphDiscuss this resultChallenge it