AFTD Auto-Formalizing Theoretical Domains

is_vertex_critical

def

A simple graph G is k-vertex-critical if its chromatic number is k and deleting any vertex yields a graph with chromatic number strictly less than k.

Statement

def is_vertex_critical {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
Defined in
arXiv:2610.40279 Section 1
Verified
07 Nov 2026
Axioms
none listed

Read back from the Lean

A simple graph G on vertex type V is defined to be vertex-critical with respect to k : ℕ (is_vertex_critical G k) if and only if: 1. The chromatic number of G equals k (coerced to ℕ∞), and 2. For every vertex v : V, the chromatic number of the induced subgraph on the complement of {v} (i.e., with vertex v removed) is strictly less than k (coerced to ℕ∞).

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 graph is k-vertex-critical if its chromatic number is k and deleting any vertex strictly reduces its chromatic number. -/
def is_vertex_critical {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop :=
  G.chromaticNumber = (k : ℕ∞) ∧ ∀ v : V, (G.induce ({v}ᶜ : Set V)).chromaticNumber < (k : ℕ∞)
See it in the graphDiscuss this resultChallenge it