AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_far_colorable

def

A finite simple graph G on vertex type V is ε-far from being k-colorable if for every edge subset E' ⊆ E(G), whenever deleting E' from G leaves a k-colorable graph, the cardinality of E' is at least ε |V|².

Statement

def simple_graph_is_far_colorable {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (ε : ℝ) : Prop
Defined in
combinatorics/2610-31489-near-optimal-bounds-for-testing-k-colorability.md:126
Verified
25 Oct 2026
Axioms
none listed
Used by 1
  • simple_graph_is_far_colorable_iffA finite simple graph G on a type V with decidable equality and decidable adjacency is ε-far from being k-colorable if and only if every…

Read back from the Lean

A definition simple_graph_is_far_colorable parameterized by: - a type V with [Fintype V] and [DecidableEq V] - a simple graph G : SimpleGraph V with [DecidableRel G.Adj] - a natural number k : ℕ - a real number ε : ℝ which asserts that: for every finset of edges E' : Finset (Sym2 V) such that E' ⊆ G.edgeFinset, if the graph obtained by deleting the edges of E' from G is k-colorable (i.e., has a proper vertex coloring with at most k colors), then ε * (Fintype.card V : ℝ)^2 ≤ (E'.card : ℝ). In other words, at least ε * |V|^2 edges must be deleted from G in order to make it k-colorable.

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 finite simple graph G is ε-far from being k-colorable if at least ε |V|² edges must be deleted from G to make it k-colorable. -/
def simple_graph_is_far_colorable {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (ε : ℝ) : Prop := ∀ E' ⊆ G.edgeFinset, (G.deleteEdges (E' : Set (Sym2 V))).Colorable k →
    ε * (Fintype.card V : ℝ) ^ 2 ≤ (E'.card : ℝ)
See it in the graphDiscuss this resultChallenge it