AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_choosable

def

A simple graph G is k-choosable if it is (k:1)-choosable, i.e., for every assignment of k-element color lists to the vertices, there exists a proper coloring choosing a color from each vertex's list.

Statement

def simple_graph_is_choosable {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
Defined in
arXiv:2611.03151, Section 1; Erdős, Rubin, Taylor (1979)
Verified
05 Nov 2026
Axioms
none listed
Built on 1
  • simple_graph_is_multiple_choosableA simple graph G is (a:b)-choosable if for every assignment L of a-element color lists (from ℕ) to the vertices of G, there exists an…
Used by 1
  • simple_graph_choice_numberThe choice number (or list chromatic number) ch(G) of a simple graph G is the infimum over all natural numbers k such that G is…

Read back from the Lean

Given a simple graph G on a type V and a natural number k, simple_graph_is_choosable G k asserts that G is (k, 1)-multiple choosable: for every assignment L : V → Finset ℕ of lists of colors such that (L v).card = k for every vertex v, there exists a choice function φ : V → Finset ℕ such that for every vertex v, φ v ⊆ L v and (φ v).card = 1, and for every pair of adjacent vertices u, v in G, φ u and φ v are disjoint.

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 simple graph is k-choosable if it is (k:1)-choosable. -/
def simple_graph_is_choosable {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop := simple_graph_is_multiple_choosable G k 1
See it in the graphDiscuss this resultChallenge it