AFTD Auto-Formalizing Theoretical Domains

ProperlyColorsKColorable

def

For an integer k and graph size n, a coloring algorithm A : SimpleGraph (Fin n) → (Fin n → ℕ) assigning natural number colors properly colors k-colorable graphs if for every simple graph G on Fin n such that G.Colorable k, for all u, v : Fin n, G.Adj u v implies A G u ≠ A G v.

Statement

def ProperlyColorsKColorable {n : ℕ} (k : ℕ) (A : SimpleGraph (Fin n) → (Fin n → ℕ)) : Prop
Defined in
arXiv:2610.41516 Section 1
Verified
02 Nov 2026
Axioms
none listed
Used by 3

Read back from the Lean

Given a natural number k and a function A that assigns to each simple graph on Fin n a vertex labeling Fin n → ℕ, ProperlyColorsKColorable k A asserts that for every simple graph G on vertices Fin n, if G is k-colorable, then for all vertices u, v : Fin n, if u is adjacent to v in G, then A G u ≠ A G v (that is, A G is a proper coloring of G).

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

/-- A coloring algorithm on Fin n assigning natural number colors properly colors k-colorable graphs if it gives a proper coloring whenever G is k-colorable. -/
def ProperlyColorsKColorable {n : ℕ} (k : ℕ) (A : SimpleGraph (Fin n) → (Fin n → ℕ)) : Prop :=
  ∀ (G : SimpleGraph (Fin n)), G.Colorable k →
    ∀ (u v : Fin n), G.Adj u v → A G u ≠ A G v
See it in the graphDiscuss this resultChallenge it