AFTD Auto-Formalizing Theoretical Domains

multigraph_truncation_not_adj

theoremverified

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.

  1. 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`).

    line 4

      fun hadj => hadj.2.elim hv he

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
See it in the graphDiscuss this resultChallenge it