AFTD Auto-Formalizing Theoretical Domains

multigraph_truncation_adj_external

theoremverified

Sanity: the two ports (u, e), (v, e) of an edge e with distinct endpoints u ≠ v are adjacent in the truncation (the external edge).

Statement

theorem multigraph_truncation_adj_external {V E : Type*} (ends : E → Sym2 V) {u v : V} {e : E}
    (hu : u ∈ ends e) (hv : v ∈ ends e) (huv : u ≠ v) :
    (multigraph_truncation ends).Adj ⟨(u, e), hu⟩ ⟨(v, e), hv⟩
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

By definition, two vertices in the truncation graph are adjacent if they are distinct and share either their vertex component or their edge component. The proof directly establishes both conjuncts for the ports ⟨(u, e), hu⟩ and ⟨(v, e), hv⟩. Distinctness holds because equality of the pairs would imply u = v by projection to the vertex component, contradicting the assumption u ≠ v; the second condition holds via Or.inr because both vertices share the edge e by reflexivity.

  1. The incidence pairs ⟨(u, e), hu⟩ and ⟨(v, e), hv⟩ are adjacent in the truncation graph.

    By definition of `multigraph_truncation`, two vertices are adjacent if they are distinct and share either their vertex endpoint or their edge. The proof supplies a pair satisfying both conditions: first, assuming the two vertices are equal, projecting to the first component via `congrArg` yields u = v, which contradicts huv (u ≠ v); second, the edge components are both e, so the equality e = e holds by reflexivity, satisfying the right disjunct of the adjacency condition via `Or.inr`.

    line 4

    uses congrArg, Or.inr

      ⟨fun hp => huv (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.1) hp), Or.inr rfl⟩
congrArg
If two arguments are equal, the values of a function applied to them are equal: if a₁ = a₂, then f a₁ = f a₂.
Or.inr
If b holds, then the disjunction a ∨ b holds.

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_adj_external {V E : Type*} (ends : E → Sym2 V) {u v : V} {e : E}    (hu : u ∈ ends e) (hv : v ∈ ends e) (huv : u ≠ v) :    (multigraph_truncation ends).Adj ⟨(u, e), hu⟩ ⟨(v, e), hv⟩ :=  ⟨fun hp => huv (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.1) hp), Or.inr rfl⟩
See it in the graphDiscuss this resultChallenge it