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 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
- group_cayley_table_chromatic_number_ne_succFor every finite group G, the chromatic number of its Cayley table Latin square graph is not equal to |G| + 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.
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.
uses
SimpleGraph.chromaticNumber_le_iff_colorable.mpclassical 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
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.
uses
Finset.coe_filter,Finset.mem_univ,true_andhave 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])
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.
uses
cayley_table_graph_indep_set_card_lehave 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
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².
uses
Finset.card_eq_sum_card_fiberwise,Finset.card_univ,Fintype.card_prodhave 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]
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.
suffices hex : ∃ i, (g i).card = n by obtain ⟨i, hi⟩ := hex exact ⟨g i, hindep i, hi⟩
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.
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
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.
uses
Finset.sum_le_sum,Finset.sum_add_distrib,Finset.sum_consthave 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
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.
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.
- The proof relies on the auxiliary lemma `cayley_table_graph_indep_set_card_le`, which states that any independent set in the Cayley table graph has cardinality at most |G|. In combinatorial terms, an independent set in a Cayley table corresponds to entries sharing no row, no column, and no product value (a partial transversal), which can have at most |G| entries.
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.
/-- 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