Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Symmetric figure-eights in Cayley graphs of noncyclic groups of odd order

Proved
CayleyErdosGyarfas.noncyclic_odd_order_symmetric_figure_eight

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

cayley-graphscombinatoricscycleserdos-gyarfasgraph-theorygroup-theory

Let GGG be a finite noncyclic group of odd order and let S⊆GS \subseteq GS⊆G be a generating set of GGG that is closed under inverses and does not contain the identity. Then

Cay⁡(G,S) contains a symmetric figure-eight,\operatorname{Cay}(G,S) \text{ contains a symmetric figure-eight},Cay(G,S) contains a symmetric figure-eight,

that is, two cycles of a common length 2n2^n2n with n≥2n \ge 2n≥2 that share exactly one vertex, one of which is the left translate gαg\alphagα of the other cycle α\alphaα for some g∈Gg \in Gg∈G, up to the choice of starting vertex. Here, for a group HHH and a subset T⊆HT \subseteq HT⊆H, Cay⁡(H,T)\operatorname{Cay}(H,T)Cay(H,T) is the Cayley graph with vertex set HHH in which distinct x,y∈Hx, y \in Hx,y∈H are adjacent when y=xty = xty=xt or x=ytx = ytx=yt for some t∈Tt \in Tt∈T; every left multiplication z↦hzz \mapsto hzz↦hz is an automorphism of it. 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.

The paper announces this after Theorem 1.1 (every Cayley graph of a noncyclic group of odd order contains a symmetric figure-eight) and proves it as the claim inside the proof of Theorem 1.1. It strengthens Theorem 1.1 for noncyclic groups. The restriction to noncyclic groups is needed: for C5=⟨c⟩C_5 = \langle c \rangleC5​=⟨c⟩, Cay⁡(C5,{c±1,c±2})=K5\operatorname{Cay}(C_5, \{c^{\pm 1}, c^{\pm 2}\}) = K_5Cay(C5​,{c±1,c±2})=K5​ has too few vertices for two such cycles.

Formalization Note The paper's claim assumes ∣S∣≥3|S| \ge 3∣S∣≥3; that hypothesis is omitted because the others imply ∣S∣≥4|S| \ge 4∣S∣≥4. In a group of odd order no nonidentity element is its own inverse, so SSS is a union of pairs {s,s−1}\{s, s^{-1}\}{s,s−1} with s≠s−1s \ne s^{-1}s=s−1; the empty set generates the trivial group and a single pair generates ⟨s⟩\langle s \rangle⟨s⟩, both cyclic, so SSS contains at least two pairs. Noncyclicity is ¬ IsCyclic G. The statement is identical, up to the spelling of the namespace, to CayleyErdősGyárfás.noncyclic_odd_order_symmetric_figure_eight in the Challenge of Palomar entry PALOMAR-2026-11-04-000015, where it is proved.

Preamble
import Definitions.Def_CayleyErdosGyarfas_HasSymmetricFigureEight
import Mathlib.GroupTheory.Nilpotent
import Mathlib.GroupTheory.PGroup
import Mathlib.Data.Set.Card
Formal statement
namespace CayleyErdosGyarfas

/-- **Noncyclic strengthening of Theorem 1.1** (arXiv:2611.05060v1, p. 1 after
Theorem 1.1, and the claim in the proof of Theorem 1.1 on p. 4). If `G` is a finite
noncyclic group of odd order and `S` is a symmetric generating set with `1 ∉ S`, then
`Cay(G, S)` contains a symmetric figure-eight. -/
theorem noncyclic_odd_order_symmetric_figure_eight
    {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 = ⊤)
    (hncyclic : ¬ IsCyclic G) : HasSymmetricFigureEight S := 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 (paragraph following Theorem 1.1) and the claim at the start of the second paragraph of the proof of Theorem 1.1 (after the cyclic case), §2, p. 4; 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 an arbitrary finite group, written multiplicatively with identity 111, and let S⊆GS \subseteq GS⊆G be an arbitrary subset. Exactly these hypotheses are assumed:

  1. ∣G∣|G|∣G∣ is odd.
  2. SSS is closed under inverses: s∈S⇒s−1∈Ss \in S \Rightarrow s^{-1} \in Ss∈S⇒s−1∈S.
  3. 1∉S1 \notin S1∈/S.
  4. SSS generates GGG, meaning the subgroup generated by SSS is all of GGG.
  5. GGG is not cyclic: there is no c∈Gc \in Gc∈G with G={cm:m∈Z}G = \{c^m : m \in \mathbb{Z}\}G={cm:m∈Z}.

Nothing else is assumed. There is no explicit lower bound on ∣S∣|S|∣S∣, no minimality or independence condition on SSS, and no further condition on GGG (for example abelian, nilpotent, or of prime-power order). The hypotheses can all hold at once, for example with G=C3×C3=⟨x⟩×⟨y⟩G = C_3 \times C_3 = \langle x\rangle \times \langle y\rangleG=C3​×C3​=⟨x⟩×⟨y⟩ and S={x±1,y±1}S = \{x^{\pm1}, y^{\pm1}\}S={x±1,y±1}; 999 is the smallest possible order. Together they force ∣S∣|S|∣S∣ to be even with ∣S∣≥4|S| \ge 4∣S∣≥4. The reason is that a group of odd order has no element of order 222, so SSS splits into pairs {s,s−1}\{s, s^{-1}\}{s,s−1} with s≠s−1s \ne s^{-1}s=s−1. Then S=∅S = \emptysetS=∅ would make GGG trivial, and S={s,s−1}S = \{s, s^{-1}\}S={s,s−1} would make G=⟨s⟩G = \langle s \rangleG=⟨s⟩ cyclic.

Let Γ\GammaΓ be the Cayley graph used here, in which generators act on the right. It is the simple graph with vertex set GGG in which x,y∈Gx, y \in Gx,y∈G are adjacent if and only if

x≠yand( y=xs for some s∈S  or  x=ys for some s∈S ),x \ne y \quad\text{and}\quad \bigl(\, y = xs \text{ for some } s \in S \ \text{ or } \ x = ys \text{ for some } s \in S \,\bigr),x=yand(y=xs for some s∈S  or  x=ys for some s∈S),

that is, x≠yx \ne yx=y and (x−1y∈Sx^{-1}y \in Sx−1y∈S or y−1x∈Sy^{-1}x \in Sy−1x∈S). By construction this relation is symmetric and has no loops, whether or not hypotheses 2 and 3 hold. Under hypotheses 2 and 3 it is equivalent to x−1y∈Sx^{-1}y \in Sx−1y∈S. So each xxx is adjacent to exactly the ∣S∣|S|∣S∣ distinct vertices xsxsxs with s∈Ss \in Ss∈S. Every left multiplication x↦gxx \mapsto gxx↦gx preserves adjacency, since (gx)−1(gy)=x−1y(gx)^{-1}(gy) = x^{-1}y(gx)−1(gy)=x−1y.

Conclusion. There exist a natural number nnn, a vertex v∈Gv \in Gv∈G, and two closed walks α\alphaα and β\betaβ in Γ\GammaΓ, each starting and ending at vvv, such that all of the conditions below hold. Write L=2nL = 2^nL=2n. Write the vertex sequence of α\alphaα as v=a0,a1,…,aL=vv = a_0, a_1, \ldots, a_L = vv=a0​,a1​,…,aL​=v and that of β\betaβ as v=b0,b1,…,bL=vv = b_0, b_1, \ldots, b_L = vv=b0​,b1​,…,bL​=v. Consecutive terms are adjacent in Γ\GammaΓ.

  • Length: n≥2n \ge 2n≥2, so L∈{4,8,16,…}L \in \{4, 8, 16, \ldots\}L∈{4,8,16,…}. Both α\alphaα and β\betaβ have exactly L=2nL = 2^nL=2n edges, with the same nnn for both.
  • Both are cycles: each is a nonempty closed walk that repeats no edge, and its vertices after the starting one (a1,…,aLa_1, \ldots, a_La1​,…,aL​, respectively b1,…,bLb_1, \ldots, b_Lb1​,…,bL​) are pairwise distinct. So vvv is the only repeated vertex, and it occurs only at the start and the end. Since L≥4L \ge 4L≥4, this amounts to the following: a1,…,aLa_1, \ldots, a_La1​,…,aL​ are LLL distinct elements with ai−1∼aia_{i-1} \sim a_iai−1​∼ai​ for 1≤i≤L1 \le i \le L1≤i≤L (where a0=aLa_0 = a_La0​=aL​), and likewise for the bib_ibi​.
  • Translation and rotation: there exist g∈Gg \in Gg∈G and k∈Nk \in \mathbb{N}k∈N such that rotating the list (ga1,ga2,…,gaL)(ga_1, ga_2, \ldots, ga_L)(ga1​,ga2​,…,gaL​) to the left by kkk positions gives exactly the list (b1,…,bL)(b_1, \ldots, b_L)(b1​,…,bL​). The number kkk comes from the definition of "is a cyclic rotation of". The rotation is by k mod Lk \bmod LkmodL, so one may take 0≤k<L0 \le k < L0≤k<L, and then
(b1,b2,…,bL)=(gak+1,…,gaL, ga1,…,gak).(b_1, b_2, \ldots, b_L) = (g a_{k+1}, \ldots, g a_L,\ g a_1, \ldots, g a_k).(b1​,b2​,…,bL​)=(gak+1​,…,gaL​, ga1​,…,gak​).

The translation is left multiplication by ggg, applied to the vertices of α\alphaα; equivalently, g−1g^{-1}g−1 applied to the vertices of β\betaβ. The two lists leave out the initial copy of vvv but keep the final one, so they are the cyclic vertex sequences of the two cycles. Only cyclic shifts are allowed, not reversals, so gαg\alphagα and β\betaβ must run in the same direction. This can always be arranged by reversing β\betaβ, since the reverse is again a cycle at vvv with the same vertices. Equivalently, the cyclic step sequences (a0−1a1,…,aL−1−1aL)(a_0^{-1}a_1, \ldots, a_{L-1}^{-1}a_L)(a0−1​a1​,…,aL−1−1​aL​) and (b0−1b1,…,bL−1−1bL)(b_0^{-1}b_1, \ldots, b_{L-1}^{-1}b_L)(b0−1​b1​,…,bL−1−1​bL​), whose entries lie in SSS, are cyclic shifts of each other. No explicit condition is placed on ggg.

  • They meet only at vvv: for every w∈Gw \in Gw∈G,
(w∈{a0,…,aL}  and  w∈{b0,…,bL})  ⟺  w=v.\bigl(w \in \{a_0, \ldots, a_L\} \ \text{ and } \ w \in \{b_0, \ldots, b_L\}\bigr) \iff w = v.(w∈{a0​,…,aL​}  and  w∈{b0​,…,bL​})⟺w=v.

The direction "⇐\Leftarrow⇐" holds automatically. The content is {a1,…,aL}∩{b1,…,bL}={v}\{a_1, \ldots, a_L\} \cap \{b_1, \ldots, b_L\} = \{v\}{a1​,…,aL​}∩{b1​,…,bL​}={v}. It follows that:

  • the two cycles share no edge;
  • together they use 2n+1−12^{n+1} - 12n+1−1 distinct elements of GGG, so 2n+1−1≤∣G∣2^{n+1} - 1 \le |G|2n+1−1≤∣G∣;
  • g≠1g \ne 1g=1, because with g=1g = 1g=1 the two vertex sets would coincide. Hence x↦gxx \mapsto gxx↦gx has no fixed points, and in particular gv≠vgv \ne vgv=v.
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