Skip to content

Erdős Problem #24

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

How many different cycles of length five can a triangle-free graph contain? Erdős Problem #24 asks whether a triangle-free graph with exactly \(5n\) vertices has at most \(n^5\) different pentagons.

The answer is yes, proved independently in 2012 and 2013. A different cycle here means a different undirected five-cycle; rotating or reversing a listing of its vertices does not create another pentagon.

A small example

Begin with a five-cycle. Replace each vertex with a class of \(n\) independent vertices. Join all pairs of vertices between neighbouring classes, and none between non-neighbouring classes.

A five-cycle in this blow-up uses one vertex from each class, so there are exactly

\[ n\times n\times n\times n\times n=n^5 \]

different pentagons. The construction remains triangle-free because an edge must join neighbouring classes of the original pentagon, which contains no triangle. It shows the claimed upper bound would be best possible.

What is known

Andrzej Grzesik, On the maximum number of five-cycles in a triangle-free graph, Journal of Combinatorial Theory, Series B 102 (2012), 1061–1066, proves

\[ \#C_5(G)\le\left(\frac{|V(G)|}{5}\right)^5 \]

for every triangle-free graph, using flag algebras. An independent proof by Hatami, Hladký, Král, Norine and Razborov also characterizes equality in terms of the balanced pentagon blow-up.

Substituting \(|V(G)|=5n\) gives exactly Erdős's proposed \(n^5\) bound. More general questions for longer odd cycles are separate problems.

GCL's current state

Source audit #1293 checks the published theorem's exact cycle-counting convention and the sharp lower construction. The old admitted GCL formal-provider snapshot contains no Problem #24 statement; an external registry's reported Lean verification has not been replayed by GCL.

What remains

Nothing remains to settle this five-cycle inequality in the mathematical literature. Further work would concern a reproducible formal or flag-algebra proof, the exact equality statement or genuinely separate longer-odd-cycle questions.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1293 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction