multigraph_truncation_adj_external
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.
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`.
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⟩