op869_online_coloring_clique_exact
For any natural number k, any coloring algorithm A : SimpleGraph (Fin k) → (Fin k → ℕ) that properly colors k-colorable graphs uses exactly k colors on some k-colorable graph on Fin k.
Statement
theorem op869_online_coloring_clique_exact (k : ℕ)
(A : SimpleGraph (Fin k) → (Fin k → ℕ))
(hprop : ProperlyColorsKColorable k A) :
∃ G : SimpleGraph (Fin k), G.Colorable k ∧ colorsUsed (A G) = k- Source
- folklore
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- ProperlyColorsKColorableFor an integer k and graph size n, a coloring algorithm A : SimpleGraph (Fin n) → (Fin n → ℕ) assigning natural number colors properly…
- colorsUsedThe number of distinct colors assigned by a vertex coloring c : Fin n → ℕ is the cardinality of the image of c on Finset.univ.
Read back from the Lean
For every natural number k, and every function A assigning a vertex coloring (Fin k → ℕ) to each simple graph on Fin k, if A properly colors every k-colorable graph on Fin k (i.e., whenever G is k-colorable, adjacent vertices u and v satisfy A G u ≠ A G v), then there exists a simple graph G on Fin k such that G is k-colorable and A G uses exactly k distinct colors.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The complete graph ⊤ on k vertices is used as the witness graph. Since its vertices can be identified directly with the k color classes via the identity map, ⊤ is k-colorable. Because every pair of distinct vertices in ⊤ is adjacent, any proper coloring produced by the algorithm must assign pairwise distinct colors to all k vertices, which forces the algorithm to use exactly k colors.
The complete graph on k vertices, ⊤, is k-colorable.
We construct an explicit k-coloring of ⊤ using the identity map id on Fin k. By SimpleGraph.top_adj, any two adjacent vertices in ⊤ are distinct, so the identity map trivially assigns them distinct color values.
uses
SimpleGraph.Coloring.mk,SimpleGraph.top_adjhave hcolor : (⊤ : SimpleGraph (Fin k)).Colorable k := ⟨SimpleGraph.Coloring.mk id (by intro v w h exact (SimpleGraph.top_adj v w).mp h)⟩
It suffices to show that the algorithm uses k colors on the complete graph ⊤.
We provide ⊤ as the witness for the existential quantifier. Since ⊤ is already known to be k-colorable, only the identity colorsUsed (A ⊤) = k remains to be proven.
refine ⟨⊤, hcolor, ?_⟩colorsUsed (A ⊤) = k reduces to showing that A ⊤ is injective on vertices.
Unfolding the definition of colorsUsed, we must determine the cardinality of the image of Finset.univ under A ⊤. By Finset.card_image_of_injOn, this image has the same cardinality as Finset.univ provided that A ⊤ is injective. Evaluating the size of Finset.univ on Fin k yields k, leaving only the injectivity of A ⊤.
uses
Finset.card_image_of_injOnunfold colorsUsed rw [Finset.card_image_of_injOn] · simp
A ⊤ assigns distinct colors to distinct vertices, completing the proof.
Let u and v be vertices such that A ⊤ u = A ⊤ v. For contradiction, suppose u ≠ v. Then u and v are adjacent in ⊤ by SimpleGraph.top_adj. Because A properly colors any k-colorable graph and ⊤ is k-colorable, A ⊤ u ≠ A ⊤ v, which contradicts the equality of their colors. Hence u = v, establishing injectivity.
uses
SimpleGraph.top_adj· intro u _ v _ huv by_contra hne exact hprop ⊤ hcolor u v ((SimpleGraph.top_adj u v).mpr hne) huv
SimpleGraph.Coloring.mk- Constructs a proper coloring of a graph from a vertex coloring function and a proof that adjacent vertices receive different colors.
SimpleGraph.top_adj- In the complete graph ⊤, two vertices are adjacent if and only if they are distinct.
Finset.card_image_of_injOn- The image of a finite set under an injective function has the same cardinality as the original set.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- On k vertices, any algorithm properly coloring k-colorable graphs uses exactly k colors on the complete graph. -/theorem op869_online_coloring_clique_exact (k : ℕ) (A : SimpleGraph (Fin k) → (Fin k → ℕ)) (hprop : ProperlyColorsKColorable k A) : ∃ G : SimpleGraph (Fin k), G.Colorable k ∧ colorsUsed (A G) = k := by have hcolor : (⊤ : SimpleGraph (Fin k)).Colorable k := ⟨SimpleGraph.Coloring.mk id (by intro v w h exact (SimpleGraph.top_adj v w).mp h)⟩ refine ⟨⊤, hcolor, ?_⟩ unfold colorsUsed rw [Finset.card_image_of_injOn] · simp · intro u _ v _ huv by_contra hne exact hprop ⊤ hcolor u v ((SimpleGraph.top_adj u v).mpr hne) huv