AFTD Auto-Formalizing Theoretical Domains

cayley_table_graph_indep_set_card_le

theoremverified

In the Latin square graph of the Cayley table of a finite group G, every independent set (partial transversal) has cardinality at most |G|.

Statement

theorem cayley_table_graph_indep_set_card_le (G : Type*) [Group G] [Fintype G]
    (s : Finset (G × G)) (h : (cayley_table_graph G).IsIndepSet (s : Set (G × G))) :
    s.card ≤ Fintype.card G
Source
arXiv:2611.13274 Section 1
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…
Used by 1

Read back from the Lean

For any finite group $G$ and any finite subset $s \subseteq G \times G$, if $s$ is an independent set in the graph cayley_table_graph G, then the cardinality of $s$ is less than or equal to the cardinality of $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 bound is proved by projecting the independent set s ⊆ G × G onto the first coordinate (the row index) in G. If two distinct vertices in s shared the same row, they would be adjacent in the Cayley table graph, contradicting the independence of s. Hence, this projection is injective, implying |s| ≤ |G|.

  1. It suffices to show that the first-coordinate projection map is injective on s.

    Rewriting the finset cardinality |s| as the cardinality of the subtype s using Fintype.card_coe, we apply Fintype.card_le_of_injective: constructing an injective map from s to G guarantees |s| ≤ |G|. The chosen map sends each element (r, c) ∈ s to its first coordinate (row) r ∈ G.

    lines 5–6

    uses Fintype.card_coe, Fintype.card_le_of_injective

      rw [← Fintype.card_coe s]
      refine Fintype.card_le_of_injective (fun x : ↥s => (x.1).1) ?_
  2. Assume for contradiction that two elements of s share the same row coordinate but are distinct.

    Let x, y ∈ s and assume their first coordinates agree (x₁ = y₁). To establish injectivity, we assume for contradiction that x ≠ y as elements of the subtype s.

    lines 7–9

      intro x y hxy
      simp only at hxy
      by_contra hne
  3. The underlying coordinate pairs in G × G are distinct.

    If the underlying pairs in G × G were equal, Subtype.ext would imply that x = y as subtype elements, directly contradicting x ≠ y.

    lines 10–12

    uses Subtype.ext

      have hne' : (x : G × G) ≠ (y : G × G) := by
        intro hh
        exact hne (Subtype.ext hh)
  4. The two elements are adjacent in the graph, contradicting independence.

    By definition, two distinct vertices in the Cayley table graph are adjacent if they share a row, a column, or a product value. Since the two pairs are distinct and share their first coordinate (via Or.inl), they are adjacent. However, both belong to the independent set s, which by definition cannot contain adjacent vertices, yielding a contradiction.

    lines 13–15

    uses Or.inl

      have hadj : (cayley_table_graph G).Adj (x : G × G) (y : G × G) :=
        ⟨hne', Or.inl hxy⟩
      exact h x.2 y.2 hne' hadj
Fintype.card_coe
The cardinality of a finset viewed as a subtype type is equal to the cardinality of the finset itself.
Fintype.card_le_of_injective
An injective map between finite types implies that the cardinality of the domain is at most the cardinality of the codomain.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Or.inl
Given a proof of P, proves the disjunction P ∨ Q.

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

/-- Every independent set in the Cayley table graph of a finite group has cardinality at most |G|. -/theorem cayley_table_graph_indep_set_card_le (G : Type*) [Group G] [Fintype G]    (s : Finset (G × G)) (h : (cayley_table_graph G).IsIndepSet (s : Set (G × G))) :    s.card ≤ Fintype.card G := by  rw [← Fintype.card_coe s]  refine Fintype.card_le_of_injective (fun x : ↥s => (x.1).1) ?_  intro x y hxy  simp only at hxy  by_contra hne  have hne' : (x : G × G) ≠ (y : G × G) := by    intro hh    exact hne (Subtype.ext hh)  have hadj : (cayley_table_graph G).Adj (x : G × G) (y : G × G) :=    ⟨hne', Or.inl hxy⟩  exact h x.2 y.2 hne' hadj
See it in the graphDiscuss this resultChallenge it