AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_equitable_coloring

def

A coloring c : V → α of a finite simple graph G is equitable (simple_graph_is_equitable_coloring G c) if for all vertices u and v with c u = c v and every color j : α, u and v have the same number of neighbors of color j in G.

Statement

def simple_graph_is_equitable_coloring {V α : Type*} [Fintype V] (G : SimpleGraph V) (c : V → α) : Prop
Defined in
arXiv:2611.18391, Section 2
Verified
16 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given a finite type V, a type α, a simple graph G on V, and a coloring function c : V → α, the proposition simple_graph_is_equitable_coloring G c asserts that: For every pair of vertices u, v : V, if u and v have the same color under c (c u = c v), then for every color j : α, the number of neighbors of u colored j (i.e., the cardinality of the finset of vertices w adjacent to u in G such that c w = j) is equal to the number of neighbors of v colored j (the cardinality of the finset of vertices w adjacent to v in G such that c w = j).

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 vertex coloring of a finite graph is equitable if vertices of the same color have the same number of neighbors of each color. -/
def simple_graph_is_equitable_coloring {V α : Type*} [Fintype V] (G : SimpleGraph V) (c : V → α) : Prop := ∀ u v : V, c u = c v → ∀ j : α,
  letI : DecidableRel G.Adj := Classical.decRel _
  letI : DecidableEq α := Classical.decEq _
  ((G.neighborFinset u).filter (fun w => c w = j)).card =
  ((G.neighborFinset v).filter (fun w => c w = j)).card
See it in the graphDiscuss this resultChallenge it