AFTD Auto-Formalizing Theoretical Domains

has_fall_coloring

def

A graph G admits a fall colouring with colours in α if it has a proper colouring c : G.Coloring α such that for every vertex v, the closed neighbourhood of v contains all colours in α.

Statement

def has_fall_coloring {V : Type*} (α : Type*) (G : SimpleGraph V) : Prop
Defined in
arXiv:2611.16649 Sec. 1, p. 2
Verified
13 Nov 2026
Axioms
none listed

Read back from the Lean

For a type V, a type α, and a simple graph G on V, has_fall_coloring α G asserts that there exists a proper coloring c of G with colors in α (a function c : V → α such that adjacent vertices have distinct colors) such that for every vertex v : V, the image under c of the closed neighborhood of v (the set consisting of v and all vertices adjacent to v) equals Set.univ (that is, every color in α appears either on v or on at least one neighbor of 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

/-- A graph admits a fall colouring with colour set α if there is a proper colouring whose image on every closed neighbourhood is univ. -/
def has_fall_coloring {V : Type*} (α : Type*) (G : SimpleGraph V) : Prop := ∃ c : G.Coloring α, ∀ v : V, c '' (insert v (G.neighborSet v)) = Set.univ
See it in the graphDiscuss this resultChallenge it