Theorem 1.1: Cayley graphs of odd-order groups satisfy Erdős–Gyárfás
ProvedCayleyErdosGyarfas.odd_order_cayley_contains_two_power_cycleLet be a finite group of odd order and let be a generating set of that is closed under inverses, does not contain the identity, and has at least three elements. Then the Cayley graph contains a cycle whose length is a power of two:
Here has vertex set , distinct being adjacent when or for some , and a cycle of length is a closed walk with whose vertices are pairwise distinct.
Under these hypotheses every vertex has exactly neighbours, so says that the minimum degree is at least three. The theorem therefore states that Cayley graphs of groups of odd order satisfy the Erdős–Gyárfás conjecture. It is the main theorem of the paper.
Formalization Note Odd order is Odd (Nat.card G) with [Finite G], generation is Subgroup.closure S = ⊤, and is S.ncard. The graph is Mathlib's SimpleGraph.mulCayley S and a cycle is a closed walk with IsCycle. The bound is kept to match the paper, although cycles have length at least . The hypothesis is needed: in the cyclic group the set is symmetric, generates and has three elements, but its Cayley graph is a triangle. The statement is identical, up to the spelling of the namespace, to CayleyErdősGyárfás.odd_order_cayley_contains_two_power_cycle in the Challenge of Palomar entry PALOMAR-2026-11-04-000015, where it is proved.
import Mathlib.Combinatorics.SimpleGraph.Cayley import Mathlib.Combinatorics.SimpleGraph.Paths import Mathlib.GroupTheory.Nilpotent import Mathlib.GroupTheory.PGroup import Mathlib.Data.Set.Card
namespace CayleyErdosGyarfas
/-- **Theorem 1.1** (arXiv:2611.05060v1, p. 1). If `G` is a finite group of odd order
and `S` is a symmetric generating set with `1 ∉ S` and `|S| ≥ 3`, then the Cayley graph
`Cay(G, S)` contains a simple cycle of length `2 ^ n` for some `n ≥ 2`. -/
theorem odd_order_cayley_contains_two_power_cycle
{G : Type*} [Group G] [Finite G] (S : Set G)
(hodd : Odd (Nat.card G))
(hinv : ∀ s ∈ S, s⁻¹ ∈ S)
(hone : (1 : G) ∉ S)
(hgen : Subgroup.closure S = ⊤)
(hcard : 3 ≤ S.ncard) :
∃ (n : ℕ) (v : G) (c : (SimpleGraph.mulCayley S).Walk v v),
2 ≤ n ∧ c.IsCycle ∧ c.length = 2 ^ n := by sorry
end CayleyErdosGyarfasRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be any finite group (not necessarily abelian) and any subset. Assume all of the following:
- the order is odd. Here is the number of elements of , and it is a genuine count because is finite.
- is closed under inverses: , so .
- the identity is not in : .
- generates : the smallest subgroup of containing is all of .
- , where is the number of elements of . This is also a genuine count: is finite because is, so the junk value that this counting function gives infinite sets cannot occur.
Let be the Cayley graph of . It is the simple (undirected, loopless) graph with vertex set in which, for ,
that is, and ( or ). Edges join to for , so generators act by multiplication on the right. This definition already makes the relation symmetric and removes loops, so would be the same graph if were replaced by . Under the hypotheses and , adjacency is simply . The neighbours of each vertex are then exactly the distinct elements with . So is -regular, and every vertex has degree at least . The generation hypothesis is equivalent to being connected.
Under these assumptions the statement asserts that there exist a natural number , a vertex , and a closed walk in from back to such that
A walk of length is a sequence of vertices with for . Its length is the number of steps (edges traversed), not the number of vertices listed. Being a cycle means three things:
- , so the walk is not the trivial one-vertex walk;
- the edges are pairwise distinct as unordered pairs;
- are pairwise distinct, so is the only repeated vertex and occurs only at the start and the end.
These conditions force : a walk of length would need a loop, and one of length would use the same edge twice. So are distinct vertices that form a cycle of length in in the usual graph-theoretic sense, as a subgraph that need not be induced. Thus the statement asserts that contains a cycle whose length is a power of , namely one of . The explicit clause follows from the other two clauses, since and are both less than .
Edge cases:
- The trivial group is excluded. There forces , which contradicts .
- Since is odd, has no element of order , so no satisfies . The elements of therefore split into pairs , so is even. Hence the hypothesis is equivalent to , and in particular .
- The hypotheses can all hold at once. For example, take the cyclic group of order with ; then is the complete graph .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.