le_simple_graph_achromatic_number
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
- simple_graph_achromatic_numberχ_a(G) is the maximum number of colours in an achromatic colouring of G.
- simple_graph_coloring_is_achromaticA proper vertex colouring with k colours is achromatic if all k colours are used and there is at least one edge between each pair of…
- Used by 3
- cubic_paley_graph_zmod_nineteen_achromatic_numberThe cubic Paley graph G_3(19) has achromatic number 9 = (19 − 1)/2, the upper bound, above the value (19 + 2)/3 = 7 conjectured for large q.
- cubic_paley_graph_zmod_thirteen_achromatic_numberThe cubic Paley graph G_3(13) has achromatic number 6 = (13 − 1)/2, the upper bound, above the value (13 + 2)/3 = 5 conjectured for large q.
- cubic_paley_graph_zmod_thirty_one_achromatic_numberThe cubic Paley graph G_3(31) has achromatic number 15 = (31 − 1)/2, the upper bound, above the value (31 + 2)/3 = 11 conjectured for…
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.
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.
uses
le_csSupdsimp [simple_graph_achromatic_number] apply le_csSup
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|.
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
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.
· 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
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.
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⟩