AFTD Auto-Formalizing Theoretical Domains

minor_edge_is_bridge

def

For a simple graph G and a partial edge-weight realization β : G.edgeSet → Option Bool, an edge e of G is a bridge in the minor G_β if it is not a loop and removing e along with all deleted edges (weight 1) disconnects its endpoints in G.

Statement

open scoped Classical in
def minor_edge_is_bridge {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 1

Read back from the Lean

Given a vertex type V, a simple graph G on V, a partial assignment β : G.edgeSet → Option Bool on the edges of G, and an edge e : G.edgeSet: minor_edge_is_bridge G β e asserts that there exist vertices u, v : V such that: 1. (e : Sym2 V) = s(u, v) (that is, u and v are the endpoints of the edge e); 2. u and v are not reachable from each other in the simple graph on V whose edges are the edges of G assigned some false by β (i.e., SimpleGraph.fromEdgeSet {s | ∃ h : s ∈ G.edgeSet, β ⟨s, h⟩ = some false}); and 3. u and v are not reachable from each other in the graph obtained from G by deleting edge e together with all edges assigned some true by β (i.e., G.deleteEdges (insert (e : Sym2 V) {s | ∃ h : s ∈ G.edgeSet, β ⟨s, h⟩ = some true})).

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 bridge in the minor G_β if it is not a loop and removing it together with weight-1 edges disconnects its endpoints. -/
def minor_edge_is_bridge {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 ∧
    ¬ (G.deleteEdges (insert (e : Sym2 V) {s | ∃ h : s ∈ G.edgeSet, β ⟨s, h⟩ = some true})).Reachable u v
See it in the graphDiscuss this resultChallenge it