AFTD Auto-Formalizing Theoretical Domains

coloring_reversal

def

For a proper coloring kappa : V -> Fin n of a simple graph G, the coloring obtained by mapping each color c to n - 1 - c is also a proper coloring.

Statement

def coloring_reversal {V : Type*} {G : SimpleGraph V} {n : ℕ}
    (κ : G.Coloring (Fin n)) : G.Coloring (Fin n)
Defined in
arXiv:2610.31785 Proposition 3.16 proof
Verified
26 Oct 2026
Axioms
none listed
Used by 1
  • coloring_reversal_weight_addThe sum of the weights of a proper coloring kappa and its color reversal coloring_reversal kappa is equal to (n - 1) times the number of…

Read back from the Lean

Given a vertex type V, a simple graph G on V, a natural number n, and a proper coloring κ : G.Coloring (Fin n), coloring_reversal defines a new proper coloring of G with colors in Fin n by mapping each vertex v : V to the color n - 1 - κ(v).

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

/-- The canonical color-reversing involution on proper n-colorings of a simple graph. -/
def coloring_reversal {V : Type*} {G : SimpleGraph V} {n : ℕ}
    (κ : G.Coloring (Fin n)) : G.Coloring (Fin n) :=
  SimpleGraph.Coloring.mk (fun v => ⟨n - 1 - (κ v).val, by omega⟩) (by
    intro u v hadj h_eq
    have h_ne := κ.valid hadj
    apply h_ne
    ext
    have h_val := congrArg Fin.val h_eq
    dsimp at h_val
    omega)
See it in the graphDiscuss this resultChallenge it