AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_strong_edge_coloring

def

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

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
See it in the graphDiscuss this resultChallenge it