Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.1: Cayley graphs of odd-order groups satisfy Erdős–Gyárfás

Proved
CayleyErdosGyarfas.odd_order_cayley_contains_two_power_cycle

by burkh4rt · Nov 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

cayley-graphscombinatoricscycleserdos-gyarfasgraph-theorygroup-theory

Let GGG be a finite group of odd order and let S⊆GS \subseteq GS⊆G be a generating set of GGG that is closed under inverses, does not contain the identity, and has at least three elements. Then the Cayley graph Cay⁡(G,S)\operatorname{Cay}(G,S)Cay(G,S) contains a cycle whose length is a power of two:

∃ n≥2:Cay⁡(G,S) contains a cycle of length 2n.\exists\, n \ge 2 : \quad \operatorname{Cay}(G,S) \text{ contains a cycle of length } 2^n .∃n≥2:Cay(G,S) contains a cycle of length 2n.

Here Cay⁡(G,S)\operatorname{Cay}(G,S)Cay(G,S) has vertex set GGG, distinct g,hg, hg,h being adjacent when h=gsh = gsh=gs or g=hsg = hsg=hs for some s∈Ss \in Ss∈S, and a cycle of length kkk is a closed walk (v0,v1,…,vk=v0)(v_0, v_1, \dots, v_k = v_0)(v0​,v1​,…,vk​=v0​) with k≥3k \ge 3k≥3 whose vertices v1,…,vkv_1, \dots, v_kv1​,…,vk​ are pairwise distinct.

Under these hypotheses every vertex has exactly ∣S∣|S|∣S∣ neighbours, so ∣S∣≥3|S| \ge 3∣S∣≥3 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 ∣S∣|S|∣S∣ is S.ncard. The graph is Mathlib's SimpleGraph.mulCayley S and a cycle is a closed walk with IsCycle. The bound n≥2n \ge 2n≥2 is kept to match the paper, although cycles have length at least 333. The hypothesis 1∉S1 \notin S1∈/S is needed: in the cyclic group C3=⟨a⟩C_3 = \langle a \rangleC3​=⟨a⟩ the set {1,a,a−1}\{1, a, a^{-1}\}{1,a,a−1} is symmetric, generates C3C_3C3​ 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.

Preamble
import Mathlib.Combinatorics.SimpleGraph.Cayley
import Mathlib.Combinatorics.SimpleGraph.Paths
import Mathlib.GroupTheory.Nilpotent
import Mathlib.GroupTheory.PGroup
import Mathlib.Data.Set.Card
Formal statement
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 CayleyErdosGyarfas
Source
M. C. Burkhart, Odd-ordered Cayley graphs satisfy Erdős–Gyárfás, arXiv:2611.05060v1 (3 Nov 2026), https://arxiv.org/abs/2611.05060v1, §1, p. 1, Theorem 1.1 (proof in §2, pp. 4–5); standing conventions of §1.1, p. 2. Lean statement as in the Challenge of Palomar entry PALOMAR-2026-11-04-000015 (https://palomar-registry.org/entry?id=PALOMAR-2026-11-04-000015).
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let GGG be any finite group (not necessarily abelian) and S⊆GS \subseteq GS⊆G any subset. Assume all of the following:

  • the order ∣G∣|G|∣G∣ is odd. Here ∣G∣|G|∣G∣ is the number of elements of GGG, and it is a genuine count because GGG is finite.
  • SSS is closed under inverses: s∈S  ⟹  s−1∈Ss \in S \implies s^{-1} \in Ss∈S⟹s−1∈S, so S−1=SS^{-1} = SS−1=S.
  • the identity is not in SSS: 1∉S1 \notin S1∈/S.
  • SSS generates GGG: the smallest subgroup of GGG containing SSS is all of GGG.
  • ∣S∣≥3|S| \ge 3∣S∣≥3, where ∣S∣|S|∣S∣ is the number of elements of SSS. This is also a genuine count: SSS is finite because GGG is, so the junk value 000 that this counting function gives infinite sets cannot occur.

Let Γ\GammaΓ be the Cayley graph of (G,S)(G,S)(G,S). It is the simple (undirected, loopless) graph with vertex set GGG in which, for u,v∈Gu, v \in Gu,v∈G,

u∼v  ⟺  u≠v  and  ∃ g∈S: (ug=v  or  vg=u),u \sim v \iff u \ne v \ \text{ and } \ \exists\, g \in S:\ \bigl(ug = v \ \text{ or } \ vg = u\bigr),u∼v⟺u=v  and  ∃g∈S: (ug=v  or  vg=u),

that is, u≠vu \ne vu=v and (u−1v∈Su^{-1}v \in Su−1v∈S or v−1u∈Sv^{-1}u \in Sv−1u∈S). Edges join uuu to ugugug for g∈Sg \in Sg∈S, so generators act by multiplication on the right. This definition already makes the relation symmetric and removes loops, so Γ\GammaΓ would be the same graph if SSS were replaced by (S∪S−1)∖{1}(S \cup S^{-1}) \setminus \{1\}(S∪S−1)∖{1}. Under the hypotheses S−1=SS^{-1} = SS−1=S and 1∉S1 \notin S1∈/S, adjacency is simply u∼v  ⟺  u−1v∈Su \sim v \iff u^{-1}v \in Su∼v⟺u−1v∈S. The neighbours of each vertex uuu are then exactly the ∣S∣|S|∣S∣ distinct elements ususus with s∈Ss \in Ss∈S. So Γ\GammaΓ is ∣S∣|S|∣S∣-regular, and every vertex has degree at least 333. The generation hypothesis is equivalent to Γ\GammaΓ being connected.

Under these assumptions the statement asserts that there exist a natural number nnn, a vertex v∈Gv \in Gv∈G, and a closed walk ccc in Γ\GammaΓ from vvv back to vvv such that

n≥2,c is a cycle,length⁡(c)=2n.n \ge 2, \qquad c \text{ is a cycle}, \qquad \operatorname{length}(c) = 2^n.n≥2,c is a cycle,length(c)=2n.

A walk of length ℓ\ellℓ is a sequence of vertices v=x0,x1,…,xℓ=vv = x_0, x_1, \dots, x_\ell = vv=x0​,x1​,…,xℓ​=v with xi−1∼xix_{i-1} \sim x_ixi−1​∼xi​ for 1≤i≤ℓ1 \le i \le \ell1≤i≤ℓ. Its length ℓ\ellℓ is the number of steps (edges traversed), not the number of vertices listed. Being a cycle means three things:

  • ℓ≥1\ell \ge 1ℓ≥1, so the walk is not the trivial one-vertex walk;
  • the ℓ\ellℓ edges {xi−1,xi}\{x_{i-1}, x_i\}{xi−1​,xi​} are pairwise distinct as unordered pairs;
  • x1,…,xℓx_1, \dots, x_\ellx1​,…,xℓ​ are pairwise distinct, so vvv is the only repeated vertex and occurs only at the start and the end.

These conditions force ℓ≥3\ell \ge 3ℓ≥3: a walk of length 111 would need a loop, and one of length 222 would use the same edge twice. So x1,…,xℓx_1, \dots, x_\ellx1​,…,xℓ​ are ℓ\ellℓ distinct vertices that form a cycle of length ℓ\ellℓ in Γ\GammaΓ in the usual graph-theoretic sense, as a subgraph that need not be induced. Thus the statement asserts that Γ\GammaΓ contains a cycle whose length is a power of 222, namely one of 4,8,16,32,…4, 8, 16, 32, \dots4,8,16,32,…. The explicit clause n≥2n \ge 2n≥2 follows from the other two clauses, since 20=12^0 = 120=1 and 21=22^1 = 221=2 are both less than 333.

Edge cases:

  • The trivial group is excluded. There 1∉S1 \notin S1∈/S forces S=∅S = \emptysetS=∅, which contradicts ∣S∣≥3|S| \ge 3∣S∣≥3.
  • Since ∣G∣|G|∣G∣ is odd, GGG has no element of order 222, so no s∈Ss \in Ss∈S satisfies s=s−1s = s^{-1}s=s−1. The elements of SSS therefore split into pairs {s,s−1}\{s, s^{-1}\}{s,s−1}, so ∣S∣|S|∣S∣ is even. Hence the hypothesis ∣S∣≥3|S| \ge 3∣S∣≥3 is equivalent to ∣S∣≥4|S| \ge 4∣S∣≥4, and in particular ∣G∣≥5|G| \ge 5∣G∣≥5.
  • The hypotheses can all hold at once. For example, take the cyclic group of order 555 with S=G∖{1}S = G \setminus \{1\}S=G∖{1}; then Γ\GammaΓ is the complete graph K5K_5K5​.
Human review
  • Endorsed by Shuze Chen · Nov 12, 2026

    Confirmed by the moderator at approval.

  • Endorsed by burkh4rt · Nov 12, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me