minor_edge_is_bridge
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
- mst_id_certificate_imp_minor_edges_loop_or_bridgeIf a partial realization β is an MST identification certificate for a connected simple graph G on a finite vertex set, then every…
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