AFTD Auto-Formalizing Theoretical Domains

multigraph_truncation

def

The 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 (parallel edges are distinct elements of E). T(G) is a SimpleGraph on the subtype of ports {p : V × E // p.1 ∈ ends p.2}, i.e. the incidences (v, e) with v an endpoint of e. Two ports p, q are adjacent iff p ≠ q ∧ (p.1.1 = q.1.1 ∨ p.1.2 = q.1.2): distinct ports at the same vertex v of G (the edges of the canonical triangle Δ_v, called internal) or distinct ports on the same edge e of G (the edge (u,e)(v,e) for e = uv, called external).

Statement

def multigraph_truncation {V E : Type*} (ends : E → Sym2 V) :
    SimpleGraph {p : V × E // p.1 ∈ ends p.2}
Defined in
arXiv:2610.41950 (Strong edge-colourings of truncations of cubic graphs), Section 1: definition of the truncation T(G) of a loopless cubic multigraph
Verified
03 Nov 2026
Axioms
none listed
Used by 4

Read back from the Lean

Given types V and E and an endpoint map ends : E → Sym2 V (representing an undirected multigraph with vertex set V and edge set E), multigraph_truncation ends defines a SimpleGraph whose vertices are pairs p = (v, e) : V × E such that v ∈ ends e (i.e., incidences of an edge and one of its endpoints). Two distinct incidence pairs p and q are adjacent if and only if they share the same vertex (p.val.1 = q.val.1) or they share the same edge (p.val.2 = q.val.2).

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

def multigraph_truncation {V E : Type*} (ends : E → Sym2 V) :
    SimpleGraph {p : V × E // p.1 ∈ ends p.2} where
  Adj p q := p ≠ q ∧ (p.1.1 = q.1.1 ∨ p.1.2 = q.1.2)
  symm := ⟨fun _ _ h => ⟨h.1.symm, h.2.imp Eq.symm Eq.symm⟩⟩
  loopless := ⟨fun _ h => h.1 rfl⟩
See it in the graphDiscuss this resultChallenge it