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
- binary_function_graph_clique_free_threeIf a simple graph G has chromatic number strictly greater than 6, then its binary function graph is triangle-free (3-clique free).
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