AFTD Auto-Formalizing Theoretical Domains

le_simple_graph_achromatic_number

theoremverified

An achromatic colouring with k colours shows χ_a(G) ≥ k (the set of such k is bounded by |V| since achromatic colourings are surjective).

Statement

theorem le_simple_graph_achromatic_number {V : Type*} [Fintype V] {G : SimpleGraph V} {k : ℕ}
    (C : G.Coloring (Fin k)) (hC : simple_graph_coloring_is_achromatic C) :
    k ≤ simple_graph_achromatic_number G
Source
sanity lemma for simple_graph_achromatic_number; serves OP-442
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 3

The proof, explained

By definition, the achromatic number χ_a(G) is the supremum of the set of numbers of colours admitting an achromatic colouring. Since every achromatic colouring is surjective, any such colouring has at most |V| colours, which shows this set is bounded above by |V|. The given colouring C witnesses that k belongs to the set, and therefore k ≤ χ_a(G) by the defining property of the supremum.

  1. It suffices to show that the set of colour counts admitting an achromatic colouring is bounded above and contains k.

    Unfolding the definition of the achromatic number as the supremum of the set of colour counts admitting an achromatic colouring of G, applying le_csSup reduces the goal to two conditions: the set must be bounded above, and k must belong to it.

    lines 4–5

    uses le_csSup

      dsimp [simple_graph_achromatic_number]
      apply le_csSup
  2. The set of colour counts admitting an achromatic colouring is bounded above by |V|.

    We show that |V| is an upper bound. Let m be any colour count with an achromatic colouring C_m : V → Fin m. By definition of achromatic colouring, C_m is surjective, so Fintype.card_le_of_surjective gives |Fin m| ≤ |V|. Since |Fin m| = m by Fintype.card_fin, this yields m ≤ |V|.

    lines 6–10

    uses Fintype.card_le_of_surjective, Fintype.card_fin

      · refine ⟨Fintype.card V, ?_⟩
        rintro m ⟨Cm, hCm⟩
        have := Fintype.card_le_of_surjective (⇑Cm) hCm.1
        rw [Fintype.card_fin] at this
        exact this
  3. k belongs to the set of colour counts admitting an achromatic colouring of G.

    The given colouring C and its achromaticity hypothesis hC supply the required witness that k is in the set.

    line 11

      · exact ⟨C, hC⟩
le_csSup
In a conditionally complete lattice, if a set s is bounded above and a ∈ s, then a ≤ sSup s.
Fintype.card_le_of_surjective
If there is a surjective map f : α → β between finite types, then |β| ≤ |α|.
Fintype.card_fin
The cardinality of Fin n is n.

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

theorem le_simple_graph_achromatic_number {V : Type*} [Fintype V] {G : SimpleGraph V} {k : ℕ}    (C : G.Coloring (Fin k)) (hC : simple_graph_coloring_is_achromatic C) :    k ≤ simple_graph_achromatic_number G := by  dsimp [simple_graph_achromatic_number]  apply le_csSup  · refine ⟨Fintype.card V, ?_⟩    rintro m ⟨Cm, hCm⟩    have := Fintype.card_le_of_surjective (⇑Cm) hCm.1    rw [Fintype.card_fin] at this    exact this  · exact ⟨C, hC⟩
See it in the graphDiscuss this resultChallenge it