simple_graph_edge_conflict
def
Two distinct edges e₁, e₂ ∈ G.edgeSet of a simple graph G conflict if they share an endpoint or are joined by an edge of G.
Statement
def simple_graph_edge_conflict {V : Type*} (G : SimpleGraph V) (e₁ e₂ : G.edgeSet) : Prop
- Defined in
- arXiv:2611.10883, Section 2
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Used by 1
- simple_graph_is_induced_matchingA set E of edges of a simple graph G is an induced matching if no two edges of E conflict in G.
Read back from the Lean
Given a type V, a simple graph G on V, and two edges e₁, e₂ : G.edgeSet, simple_graph_edge_conflict G e₁ e₂ is the proposition that:
1. e₁ ≠ e₂ (the two edges are distinct), and
2. there exists a vertex u that is an endpoint of e₁ (u ∈ (e₁ : Sym2 V)) and a vertex v that is an endpoint of e₂ (v ∈ (e₂ : Sym2 V)) such that either u = v (the edges share an endpoint) or G.Adj u v (u and v are adjacent in G).
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
/-- Two distinct edges in a graph conflict if they share an endpoint or are joined by an edge. -/ def simple_graph_edge_conflict {V : Type*} (G : SimpleGraph V) (e₁ e₂ : G.edgeSet) : Prop := e₁ ≠ e₂ ∧ ∃ u ∈ (e₁ : Sym2 V), ∃ v ∈ (e₂ : Sym2 V), u = v ∨ G.Adj u v