minor_edge_is_loop
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
- minor_edge_not_loop_of_all_noneSanity check: if no edge has been queried (every edge is assigned weight none), then no edge of G is a loop in the minor G_β.
- 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 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