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 : ℕ∞)