AFTD Auto-Formalizing Theoretical Domains

graph_color_sets

def

Given a finite vertex type V, a simple graph G on V, and a list assignment L : V → Finset ℕ assigning each vertex a finite set of colors in ℕ, graph_color_sets G L is the Finset of Finset ℕ consisting of all image sets Finset.image φ Finset.univ of proper L-colorings φ : V → ℕ of G satisfying φ(v) ∈ L(v) for all v and φ(u) ≠ φ(v) for all adjacent u, v.

Statement

noncomputable def graph_color_sets {V : Type*} [Fintype V]
    (G : SimpleGraph V) (L : V → Finset ℕ) : Finset (Finset ℕ)
Defined in
arXiv:2611.07924, Section 1
Verified
06 Nov 2026
Axioms
none listed
Used by 1
  • graph_min_color_setsFor a finite vertex type V, a simple graph G on V, and an integer m, graph_min_color_sets G m is the infimum sInf of the cardinalities…

Read back from the Lean

Given a finite type V, a simple graph G with vertex set V, and a list assignment L : V → Finset ℕ mapping each vertex to a finite set of natural numbers (colors), graph_color_sets G L is defined as the finite set of all subsets of colors (as Finset ℕ) that can be achieved as the range/image of some proper list-coloring of G from L. That is, it is the set of all Finset.image φ Finset.univ for functions φ : V → ℕ satisfying: 1. φ v ∈ L v for all v : V, and 2. φ u ≠ φ v for all vertices u, v : V such that G.Adj u 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 Finset of all color sets φ(V) of proper L-colorings φ of a graph G with lists in ℕ. -/
noncomputable def graph_color_sets {V : Type*} [Fintype V]
    (G : SimpleGraph V) (L : V → Finset ℕ) : Finset (Finset ℕ) := by
  classical
  exact (Fintype.piFinset L).filter (fun φ => ∀ u v, G.Adj u v → φ u ≠ φ v) |>.image (fun φ => Finset.image φ Finset.univ)
See it in the graphDiscuss this resultChallenge it