AFTD Auto-Formalizing Theoretical Domains

colorable_of_exists_indep_cover

lemmaverified

If the vertex set of a graph G can be covered by k independent sets, then G is k-colorable.

Statement

lemma colorable_of_exists_indep_cover {V : Type*} (G : SimpleGraph V) {k : ℕ} (S : Fin k → Set V) (hS_indep : ∀ i, G.IsIndepSet (S i)) (hS_cover : ∀ v : V, ∃ i, v ∈ S i) : G.Colorable k
Source
folklore
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

Let $V$ be a type, $G$ a simple graph with vertex type $V$, and $k$ a natural number. Given a family of subsets $S : \text{Fin } k \to \text{Set } V$, if each $S(i)$ is an independent set of vertices in $G$ for every $i \in \text{Fin } k$, and the family covers $V$ (meaning for every vertex $v \in V$, there exists some $i \in \text{Fin } k$ such that $v \in S(i)$), then $G$ is $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 graph whose vertices are covered by k independent sets is k-colorable. -/
lemma colorable_of_exists_indep_cover {V : Type*} (G : SimpleGraph V) {k : ℕ} (S : Fin k → Set V) (hS_indep : ∀ i, G.IsIndepSet (S i)) (hS_cover : ∀ v : V, ∃ i, v ∈ S i) : G.Colorable k := by
  classical
  let c : V → Fin k := fun v => Classical.choose (hS_cover v)
  have hc : ∀ v, v ∈ S (c v) := fun v => Classical.choose_spec (hS_cover v)
  refine ⟨⟨c, ?_⟩⟩
  intro v w hvw
  rw [SimpleGraph.completeGraph_eq_top, SimpleGraph.top_adj]
  intro h
  have hneq : v ≠ w := fun h' => G.ne_of_adj hvw h'
  have hmem : v ∈ S (c w) := h ▸ hc v
  exact (hS_indep (c w)) hmem (hc w) hneq hvw
See it in the graphDiscuss this resultChallenge it