AFTD Auto-Formalizing Theoretical Domains

group_cayley_table_chromatic_number_ne_succ

theoremverifiedformalization

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

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.

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

    lines 4–5

    uses le_of_eq

      intro h
      have hle : (cayley_table_graph G).chromaticNumber ≤ (Fintype.card G : ℕ∞) + 1 := le_of_eq h
  2. 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.

    lines 6–7

    uses cayley_table_graph_exists_transversal_of_chromatic_number_le_succ

      obtain ⟨s, hindep, hcard⟩ :=
        cayley_table_graph_exists_transversal_of_chromatic_number_le_succ G hle
  3. The group G admits a complete mapping.

    By cayley_table_graph_exists_complete_mapping_of_transversal, the transversal s induces a complete mapping θ on G.

    lines 8–9

    uses cayley_table_graph_exists_complete_mapping_of_transversal

      obtain ⟨θ, hθ⟩ :=
        cayley_table_graph_exists_complete_mapping_of_transversal G s hindep hcard
  4. The 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|.

    lines 10–11

    uses cayley_table_graph_chromatic_number_le_card_of_complete_mapping

      have hle' : (cayley_table_graph G).chromaticNumber ≤ (Fintype.card G : ℕ∞) :=
        cayley_table_graph_chromatic_number_le_card_of_complete_mapping G θ hθ
  5. 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).

    lines 12–15

    uses ENat.natCast_le_natCast.mp

      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)
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 ℕ.

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

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