simple_graph_is_equitable_coloring
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
- simple_graph_injective_is_equitable_coloringFor every finite simple graph G on type V and every injective function c : V → α, c satisfies simple_graph_is_equitable_coloring G c.
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