group_cayley_table_chromatic_number_ne_succ
For every finite group G, the chromatic number of its Cayley table Latin square graph is not equal to |G| + 1.
Statement
theorem group_cayley_table_chromatic_number_ne_succ (G : Type*) [Group G] [Fintype G] : (cayley_table_graph G).chromaticNumber ≠ Fintype.card G + 1
- Formalizes
- arXiv:2611.13274 Theorem 4.22 (On the Chromatic Number of Cayley Tables of Dihedral Groups)
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- cayley_table_graphThe Latin square graph of the Cayley table of a magma G is the simple graph with vertex set G × G where two distinct vertices (g₁, h₁) and…
- group_is_complete_mappingA complete mapping of a group G is a permutation θ of G such that x ↦ xθ(x) is also a permutation of G.
- cayley_table_graph_exists_transversal_of_chromatic_number_le_succIf the chromatic number of the Cayley table graph of a finite group G is at most |G| + 1, then the Cayley table has a transversal (an…
- cayley_table_graph_exists_complete_mapping_of_transversalIf the Cayley table graph of a finite group G contains a transversal of cardinality |G|, then G admits a complete mapping.
- cayley_table_graph_chromatic_number_le_card_of_complete_mappingIf a finite group G admits a complete mapping, then the chromatic number of its Cayley table graph is at most |G|.
Read back from the Lean
For every finite group $G$, the chromatic number of the Cayley table graph of $G$ (cayley_table_graph G) is not equal to $|G| + 1$ (the cardinality of $G$ plus one).
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
We proceed by contradiction: suppose the chromatic number of the Cayley table graph of G equals |G| + 1. Because this bound is at most |G| + 1, the graph contains an independent set of size |G|, which corresponds to a transversal of the Cayley table. This transversal yields a complete mapping on G, which in turn shows that the graph can be properly colored with at most |G| colors. This forces |G| + 1 ≤ |G|, an immediate contradiction.
Assume for contradiction that the chromatic number equals |G| + 1, which implies it is at most |G| + 1.
Suppose, for contradiction, that the chromatic number of the Cayley table graph of G equals |G| + 1 (hypothesis h). Applying le_of_eq immediately gives the inequality χ ≤ |G| + 1 (hypothesis hle).
uses
le_of_eqintro h have hle : (cayley_table_graph G).chromaticNumber ≤ (Fintype.card G : ℕ∞) + 1 := le_of_eq h
The Cayley table graph contains an independent set of size |G|.
From the upper bound χ ≤ |G| + 1, the lemma cayley_table_graph_exists_transversal_of_chromatic_number_le_succ provides an independent set s of size |G|, corresponding to a transversal in the Cayley table.
uses
cayley_table_graph_exists_transversal_of_chromatic_number_le_succobtain ⟨s, hindep, hcard⟩ := cayley_table_graph_exists_transversal_of_chromatic_number_le_succ G hleThe group G admits a complete mapping.
By cayley_table_graph_exists_complete_mapping_of_transversal, the transversal s induces a complete mapping θ on G.
uses
cayley_table_graph_exists_complete_mapping_of_transversalobtain ⟨θ, hθ⟩ := cayley_table_graph_exists_complete_mapping_of_transversal G s hindep hcardThe chromatic number of the Cayley table graph is at most |G|.
By cayley_table_graph_chromatic_number_le_card_of_complete_mapping, the existence of the complete mapping θ implies that the graph can be partitioned into |G| independent sets, bounding its chromatic number above by |G|.
uses
cayley_table_graph_chromatic_number_le_card_of_complete_mappinghave hle' : (cayley_table_graph G).chromaticNumber ≤ (Fintype.card G : ℕ∞) := cayley_table_graph_chromatic_number_le_card_of_complete_mapping G θ hθA contradiction is obtained from |G| + 1 ≤ |G|.
Substituting the assumption χ = |G| + 1 into the bound χ ≤ |G| yields |G| + 1 ≤ |G| in ℕ∞. Pushing the coercion through addition and applying ENat.natCast_le_natCast.mp turns this into |G| + 1 ≤ |G| in ℕ, which is impossible by linear integer arithmetic (omega).
uses
ENat.natCast_le_natCast.mprw [h] at hle' have key : ((Fintype.card G + 1 : ℕ) : ℕ∞) ≤ (Fintype.card G : ℕ∞) := by simpa using hle' exact absurd (ENat.natCast_le_natCast.mp key) (by omega)
le_of_eq- If a = b, then a ≤ b.
cayley_table_graph_exists_transversal_of_chromatic_number_le_succ- If the chromatic number of the Cayley table graph of a finite group G is at most |G| + 1, then the graph contains an independent set (transversal) of size |G|.
cayley_table_graph_exists_complete_mapping_of_transversal- An independent set of size |G| in the Cayley table graph of G yields a complete mapping on G.
cayley_table_graph_chromatic_number_le_card_of_complete_mapping- If a finite group G admits a complete mapping, then the chromatic number of its Cayley table graph is at most |G|.
ENat.natCast_le_natCast.mp- If the cast of a natural number a into ℕ∞ is at most the cast of b, then a ≤ b in ℕ.
- In Lean, graph chromatic numbers take values in the extended natural numbers (ℕ∞ = WithTop ℕ). Lines 13–15 perform casts (via simpa and ENat.natCast_le_natCast.mp) to convert the inequality |G| + 1 ≤ |G| from ℕ∞ to ℕ before closing the contradiction with linear arithmetic (omega).
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.
/-- The chromatic number of the Cayley table Latin square graph of a finite group G is never |G| + 1. -/theorem group_cayley_table_chromatic_number_ne_succ (G : Type*) [Group G] [Fintype G] : (cayley_table_graph G).chromaticNumber ≠ Fintype.card G + 1 := by intro h have hle : (cayley_table_graph G).chromaticNumber ≤ (Fintype.card G : ℕ∞) + 1 := le_of_eq h obtain ⟨s, hindep, hcard⟩ := cayley_table_graph_exists_transversal_of_chromatic_number_le_succ G hle obtain ⟨θ, hθ⟩ := cayley_table_graph_exists_complete_mapping_of_transversal G s hindep hcard have hle' : (cayley_table_graph G).chromaticNumber ≤ (Fintype.card G : ℕ∞) := cayley_table_graph_chromatic_number_le_card_of_complete_mapping G θ hθ rw [h] at hle' have key : ((Fintype.card G + 1 : ℕ) : ℕ∞) ≤ (Fintype.card G : ℕ∞) := by simpa using hle' exact absurd (ENat.natCast_le_natCast.mp key) (by omega)