In Problem 6 I ask (among other questions) whether it is true that every graph of (2k+1)n vertices, the smallest odd cycle of which has size ≥ 2k+1, can be made bipartite by omitting at most n^2 edges. This is still open for every k ≥ 1. I also ask whether such a graph can have at most n^2k+1 cycles of size 2k+1.

Erdős Problem #24 — Edge deletion and cycle counts in graphs of odd girth 2k+1

Erdős posed the conjecture in 1984. It asserts that a triangle-free graph on $5n$ vertices has at most $n^5$ copies of $C_5$ ; equality is attained by the balanced blow-up of $C_5$ .

Known results

Flag-algebra methods proved the asymptotic bound $(N/5)^5$ for triangle-free graphs on $N$ vertices (Grzesik, 2012; independently Hatami, Hladký, Král’, Norin, and Razborov, 2013).
For $5mod N=0$ , equality requires the balanced blow-up of $C_5$ .
An earlier purported all- $N$ proof contained an uncorrected error; a sporadic $N=8$ example was later identified as the Möbius ladder $ML_8$ .

2017 exact resolution

A later paper settled every finite case, proving the maximum is

\prod_{i=0}^{4}\left\lfloor\frac{N+i}{5}\right\rfloor.

For $N\geq 5$ , the only extremal graphs are balanced blow-ups of $C_5$ , except that $ML_8$ is also extremal when $N=8$ .

Current status (as of March 2026): The stated $5n$ -vertex problem is completely resolved affirmatively, with equality exactly for the balanced blow-up of $C_5$ .

Erdős Problem #24 — Edge deletion and cycle counts in graphs of odd girth $2k+1$

Primary source

Additional references

Progress summary

Solutions 0