multigraph_truncation
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
- multigraph_truncation_adj_externalSanity: the two ports (u, e), (v, e) of an edge e with distinct endpoints u ≠ v are adjacent in the truncation (the external edge).
- truncation_local_states_strong_coloring_iffLemma 2.1 of arXiv:2610.41950. Let G be a loopless cubic multigraph, given by ends : E → Sym2 V (no Fintype or Finite instance on V or E…
- multigraph_truncation_not_adjSanity: ports at different vertices and on different edges of G are not adjacent in the truncation.
- truncation_local_states_define_strong_coloringThe local states (c, h), with c h : V → E → Ω, define a strong edge-colouring of the truncation multigraph_truncation ends: there is χ :…
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⟩