multigraph_truncation_not_adj
Sanity: ports at different vertices and on different edges of G are not adjacent in the truncation.
Statement
theorem multigraph_truncation_not_adj {V E : Type*} (ends : E → Sym2 V) (p q : {p : V × E // p.1 ∈ ends p.2}) (hv : p.1.1 ≠ q.1.1) (he : p.1.2 ≠ q.1.2) : ¬ (multigraph_truncation ends).Adj p q
- Source
- sanity lemma for multigraph_truncation
- Verified
- 04 Nov 2026
- Axioms
Quot.soundpropext- Built on 1
- multigraph_truncationThe truncation T(G) of a multigraph G with vertex type V and edge type E, the multigraph given by its endpoint map ends : E → Sym2 V…
The proof, explained
The proof proceeds by contradiction: suppose the ports p and q are adjacent in the truncated multigraph. By definition of the truncation, adjacent ports must share either the same vertex or the same edge. Both cases immediately contradict the hypotheses that p and q lie on different vertices and different edges.
The ports p and q are not adjacent.
Assume for contradiction that p and q are adjacent (`hadj`). By definition of `multigraph_truncation`, adjacency implies that either the vertices coincide (p.1.1 = q.1.1) or the edges coincide (p.1.2 = q.1.2). Performing case analysis on this disjunction, the first case contradicts the hypothesis that the vertices are distinct (`hv`), and the second contradicts the hypothesis that the edges are distinct (`he`).
fun hadj => hadj.2.elim hv he
- The definition of adjacency in `multigraph_truncation` unfolds definitionally in Lean, allowing the disjunction `p.1.1 = q.1.1 ∨ p.1.2 = q.1.2` to be eliminated directly without an explicit rewrite.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem multigraph_truncation_not_adj {V E : Type*} (ends : E → Sym2 V) (p q : {p : V × E // p.1 ∈ ends p.2}) (hv : p.1.1 ≠ q.1.1) (he : p.1.2 ≠ q.1.2) : ¬ (multigraph_truncation ends).Adj p q := fun hadj => hadj.2.elim hv he