AFTD Auto-Formalizing Theoretical Domains

cayley_table_graph_exists_transversal_of_chromatic_number_le_succ

theoremverifiedformalization

If 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 independent set of cardinality |G|).

Statement

theorem cayley_table_graph_exists_transversal_of_chromatic_number_le_succ
    (G : Type*) [Group G] [Fintype G]
    (h : (cayley_table_graph G).chromaticNumber ≤ Fintype.card G + 1) :
    ∃ s : Finset (G × G), (cayley_table_graph G).IsIndepSet (s : Set (G × G)) ∧ s.card = Fintype.card G
Formalizes
arXiv:2611.13274 Proposition 1.2
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • cayley_table_graph_indep_set_card_leIn the Latin square graph of the Cayley table of a finite group G, every independent set (partial transversal) has cardinality at most |G|.
Used by 1

Read back from the Lean

Let $G$ be a finite group. If the chromatic number of the Cayley table graph of $G$ (cayley_table_graph G) is at most $|G| + 1$, then there exists a finite subset $s \subseteq G \times G$ of cardinality $|G|$ that is an independent set in cayley_table_graph G.

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 proof proceeds by contradiction using an average-size counting argument (the pigeonhole principle). Given an (n + 1)-coloring of the Cayley table graph with n = |G|, the n² vertices are partitioned into n + 1 color classes, each of which is an independent set of size at most n. If every color class had size strictly less than n, the total number of vertices would be at most (n + 1)(n - 1) = n² - 1, strictly less than the actual vertex count n². Hence at least one color class must have size exactly n, yielding the desired transversal.

  1. Fix n = |G| and obtain a proper (n + 1)-coloring of the Cayley table graph, partitioning the vertex set G × G into n + 1 color classes g(0), …, g(n).

    Since the chromatic number is at most n + 1, SimpleGraph.chromaticNumber_le_iff_colorable.mp provides a proper coloring c : G × G → Fin (n + 1). We define each color class g(i) as the fiber of vertices assigned color i.

    lines 6–11

    uses SimpleGraph.chromaticNumber_le_iff_colorable.mp

      classical
      have hcol : (cayley_table_graph G).Colorable (Fintype.card G + 1) :=
        SimpleGraph.chromaticNumber_le_iff_colorable.mp h
      obtain ⟨c⟩ := hcol
      set n := Fintype.card G with hn
      set g : Fin (n + 1) → Finset (G × G) := fun i => Finset.univ.filter (fun v => c v = i) with hg
  2. Each color class g(i) is an independent set in the Cayley table graph.

    By definition, all vertices in g(i) share the color i. Because c is a proper coloring, any adjacent pair of vertices must receive distinct colors, so no two vertices in g(i) can be adjacent.

    lines 12–18

    uses Finset.coe_filter, Finset.mem_univ, true_and

      have hindep : ∀ i, (cayley_table_graph G).IsIndepSet (g i : Set (G × G)) := by
        intro i
        intro v hv w hw hne hadj
        simp only [hg, Finset.coe_filter, Finset.mem_univ, true_and] at hv hw
        have hthis := c.map_adj hadj
        have hne' : c v ≠ c w := hthis
        exact hne' (by rw [hv, hw])
  3. Each color class g(i) has cardinality at most n.

    Applying the lemma cayley_table_graph_indep_set_card_le to each independent set g(i) gives |g(i)| ≤ |G| = n.

    lines 19–22

    uses cayley_table_graph_indep_set_card_le

      have hle : ∀ i, (g i).card ≤ n := by
        intro i
        have := cayley_table_graph_indep_set_card_le G (g i) (hindep i)
        simpa [hn] using this
  4. The sum of the cardinalities of all n + 1 color classes is n².

    The fibers of c partition the vertex set G × G, so Finset.card_eq_sum_card_fiberwise equates the sum of their sizes to |G × G|. By Finset.card_univ and Fintype.card_prod, |G × G| = |G| · |G| = n².

    lines 23–26

    uses Finset.card_eq_sum_card_fiberwise, Finset.card_univ, Fintype.card_prod

      have hcard := Finset.card_eq_sum_card_fiberwise (s := (Finset.univ : Finset (G × G)))
        (t := (Finset.univ : Finset (Fin (n + 1)))) (f := c) (fun x _ => Finset.mem_univ _)
      have hsum : ∑ i : Fin (n + 1), (g i).card = n * n := by
        rw [← hcard, Finset.card_univ, Fintype.card_prod, hn]
  5. It suffices to show that some color class g(i) has cardinality exactly n.

    If any color class g(i) has size n, then g(i) is an independent set of size |G|, providing the required transversal.

    lines 27–29

      suffices hex : ∃ i, (g i).card = n by
        obtain ⟨i, hi⟩ := hex
        exact ⟨g i, hindep i, hi⟩
  6. Assuming for contradiction that no color class has size n, every color class satisfies |g(i)| + 1 ≤ n.

    Each color class has size at most n and size not equal to n; hence |g(i)| ≤ n - 1, which in natural-number arithmetic is |g(i)| + 1 ≤ n.

    lines 30–35

      by_contra hcon
      have hlt : ∀ i, (g i).card + 1 ≤ n := by
        intro i
        have h1 := hle i
        have h2 : (g i).card ≠ n := fun hh => hcon ⟨i, hh⟩
        omega
  7. Summing the bounds |g(i)| + 1 ≤ n over all n + 1 color classes yields n² + (n + 1) ≤ (n + 1)n.

    Summing the inequalities via Finset.sum_le_sum gives ∑ (|g(i)| + 1) ≤ ∑ n. On the left, Finset.sum_add_distrib and the known sum ∑ |g(i)| = n² simplify the sum to n² + (n + 1). On the right, Finset.sum_const evaluates the sum of the constant n over n + 1 terms to (n + 1)n.

    lines 36–43

    uses Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const

      have hstep : ∑ i : Fin (n+1), ((g i).card + 1) ≤ ∑ i : Fin (n+1), n :=
        Finset.sum_le_sum (fun i _ => hlt i)
      have hleft : ∑ i : Fin (n+1), ((g i).card + 1) = n*n + (n+1) := by
        rw [Finset.sum_add_distrib, hsum]
        simp
      have hright : ∑ i : Fin (n+1), n = (n+1)*n := by
        simp [Finset.sum_const]
      rw [hleft, hright] at hstep
  8. The inequality leads to an arithmetic contradiction.

    Expanding (n + 1)n = n² + n gives n² + n + 1 ≤ n² + n, which simplifies to 1 ≤ 0, an impossibility closed by omega.

    lines 44–47

      have hfin : n*n + (n+1) ≤ n*n + n := by
        calc n*n + (n+1) ≤ (n+1)*n := hstep
        _ = n*n + n := by ring
      omega
SimpleGraph.chromaticNumber_le_iff_colorable.mp
A simple graph has chromatic number at most k if and only if it admits a proper k-coloring.
Finset.coe_filter
The coercion to a set of a filtered finite set {x ∈ s | p x} equals {x | x ∈ s ∧ p x}.
Finset.mem_univ
Every element of a finite type is a member of its universal finset.
true_and
The propositional identity stating that (True ∧ p) simplifies to p.
cayley_table_graph_indep_set_card_le
Any independent set of vertices in the Cayley table graph of a finite group G has cardinality at most |G|.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set s is equal to the sum over b ∈ t of the cardinalities of the fibers {a ∈ s | f a = b}, provided f maps s into t.
Finset.card_univ
The cardinality of the universal finset on a finite type α equals Fintype.card α.
Fintype.card_prod
The cardinality of the Cartesian product α × β of two finite types is the product of their respective cardinalities.
Finset.sum_le_sum
If f(i) ≤ g(i) for all indices i in a finite set s, then the sum of f(i) over s is at most the sum of g(i) over s.
Finset.sum_add_distrib
The sum of a pointwise sum f(x) + g(x) over a finite set equals the sum of f(x) plus the sum of g(x).
Finset.sum_const
The sum of a constant value b over a finite set s equals |s| • b.

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

/-- If the chromatic number of the Cayley table graph is at most |G| + 1, then the table contains a transversal. -/theorem cayley_table_graph_exists_transversal_of_chromatic_number_le_succ    (G : Type*) [Group G] [Fintype G]    (h : (cayley_table_graph G).chromaticNumber ≤ Fintype.card G + 1) :    ∃ s : Finset (G × G), (cayley_table_graph G).IsIndepSet (s : Set (G × G)) ∧ s.card = Fintype.card G := by  classical  have hcol : (cayley_table_graph G).Colorable (Fintype.card G + 1) :=    SimpleGraph.chromaticNumber_le_iff_colorable.mp h  obtain ⟨c⟩ := hcol  set n := Fintype.card G with hn  set g : Fin (n + 1) → Finset (G × G) := fun i => Finset.univ.filter (fun v => c v = i) with hg  have hindep : ∀ i, (cayley_table_graph G).IsIndepSet (g i : Set (G × G)) := by    intro i    intro v hv w hw hne hadj    simp only [hg, Finset.coe_filter, Finset.mem_univ, true_and] at hv hw    have hthis := c.map_adj hadj    have hne' : c v ≠ c w := hthis    exact hne' (by rw [hv, hw])  have hle : ∀ i, (g i).card ≤ n := by    intro i    have := cayley_table_graph_indep_set_card_le G (g i) (hindep i)    simpa [hn] using this  have hcard := Finset.card_eq_sum_card_fiberwise (s := (Finset.univ : Finset (G × G)))    (t := (Finset.univ : Finset (Fin (n + 1)))) (f := c) (fun x _ => Finset.mem_univ _)  have hsum : ∑ i : Fin (n + 1), (g i).card = n * n := by    rw [← hcard, Finset.card_univ, Fintype.card_prod, hn]  suffices hex : ∃ i, (g i).card = n by    obtain ⟨i, hi⟩ := hex    exact ⟨g i, hindep i, hi⟩  by_contra hcon  have hlt : ∀ i, (g i).card + 1 ≤ n := by    intro i    have h1 := hle i    have h2 : (g i).card ≠ n := fun hh => hcon ⟨i, hh⟩    omega  have hstep : ∑ i : Fin (n+1), ((g i).card + 1) ≤ ∑ i : Fin (n+1), n :=    Finset.sum_le_sum (fun i _ => hlt i)  have hleft : ∑ i : Fin (n+1), ((g i).card + 1) = n*n + (n+1) := by    rw [Finset.sum_add_distrib, hsum]    simp  have hright : ∑ i : Fin (n+1), n = (n+1)*n := by    simp [Finset.sum_const]  rw [hleft, hright] at hstep  have hfin : n*n + (n+1) ≤ n*n + n := by    calc n*n + (n+1) ≤ (n+1)*n := hstep    _ = n*n + n := by ring  omega
See it in the graphDiscuss this resultChallenge it