simple_graph_is_strong_edge_coloring
For a simple graph G on W and a colour map χ : Sym2 W → Ω (a colour for each unordered pair; only its values on edges of G matter), χ is a strong edge-colouring of G: for all x, y ∈ G.edgeSet with x ≠ y that are in strong conflict -- they share an endpoint (∃ a, a ∈ x ∧ a ∈ y), or some endpoint a of x and some endpoint b of y are adjacent in G -- we have χ x ≠ χ y. Equivalently, distinct edges at distance at most two in the line graph get distinct colours.
Statement
def simple_graph_is_strong_edge_coloring {W Ω : Type*} (G : SimpleGraph W) (χ : Sym2 W → Ω) : Prop
- Defined in
- arXiv:2610.41950 (Strong edge-colourings of truncations of cubic graphs), Section 1: definition of strong edge-colouring and strong conflict
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 3
- 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…
- simple_graph_is_strong_edge_coloring_of_injectiveSanity: a colouring giving all pairs distinct colours is a strong edge-colouring.
- 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
For types W and Ω, a simple graph G on vertex type W, and an assignment χ : Sym2 W → Ω of colors to pairs of vertices, simple_graph_is_strong_edge_coloring G χ asserts that:
For every pair of edges x, y ∈ G.edgeSet, if x ≠ y and either:
1. x and y share an endpoint (there exists a : W such that a ∈ x and a ∈ y), or
2. an endpoint of x is adjacent in G to an endpoint of y (there exist a, b : W such that a ∈ x, b ∈ y, and G.Adj a b),
then χ x ≠ χ y (the colors of x and y are distinct).
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 simple_graph_is_strong_edge_coloring {W Ω : Type*} (G : SimpleGraph W) (χ : Sym2 W → Ω) : Prop := ∀ x ∈ G.edgeSet, ∀ y ∈ G.edgeSet, x ≠ y → ((∃ a, a ∈ x ∧ a ∈ y) ∨ ∃ a b, a ∈ x ∧ b ∈ y ∧ G.Adj a b) → χ x ≠ χ y