AFTD Auto-Formalizing Theoretical Domains

op869_online_coloring_clique_exact

theoremverified

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.

  1. 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.

    lines 6–9

    uses SimpleGraph.Coloring.mk, SimpleGraph.top_adj

      have hcolor : (⊤ : SimpleGraph (Fin k)).Colorable k :=
        ⟨SimpleGraph.Coloring.mk id (by
          intro v w h
          exact (SimpleGraph.top_adj v w).mp h)⟩
  2. 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.

    line 10

      refine ⟨⊤, hcolor, ?_⟩
  3. 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 ⊤.

    lines 11–13

    uses Finset.card_image_of_injOn

      unfold colorsUsed
      rw [Finset.card_image_of_injOn]
      · simp
  4. 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.

    lines 14–16

    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

/-- 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
See it in the graphDiscuss this resultChallenge it