Densest graphs without triangles or 4-cycles on 54 or more vertices

How many edges can a graph on $n$ vertices have if it contains no cycle of length 3 or 4? The exact answer is known for every $n \le 53$, after computer searches by Brendan McKay in 2022 and 2023, and the first open case is $n = 54$.

Problem

The girth of a graph is the length of its shortest cycle. Let $f(n)$ be the largest number of edges in a simple graph on $n$ vertices with girth at least 5, that is, with no triangle and no 4-cycle (OEIS A006856). Determine $f(54)$, and more generally $f(n)$ for $n \ge 54$. CSPLib also asks for the number of non-isomorphic graphs attaining $f(n)$, and for the analogous values with larger forbidden girth.

Background

The question is CSPLib problem 52, proposed by Michael Codish, Alice Miller, Patrick Prosser and Peter Stuckey. Garnick, Kwong and Lazebnik (1993) determined $f(n)$ for $n \le 24$ and gave constructive lower bounds up to $n = 200$; later searches pushed the exact values to $n = 32$. The extremal graphs include famous objects: the unique graph attaining $f(50) = 175$ is the Hoffman–Singleton graph. The growth of $f(n)$ for large $n$, whether $f(n) \sim (n/2)^{3/2}$, is Erdős Problem #573 and is a different, asymptotic question from the exact values asked here.

What is known

• Values for $n = 1, \dots, 53$ are listed in the OEIS; for example $f(32) = 85$, $f(50) = 175$, $f(52) = 178$ and $f(53) = 181$.
• Brendan McKay computed $f(33), \dots, f(52)$ in March 2022 and $f(53)$ in January 2023.
• McKay also reported the lower bounds $f(54) \ge 185$, $f(55) \ge 189$ and $f(56) \ge 193$ (January 2023), so the open question for $n = 54$ is whether some graph of girth at least 5 has 186 or more edges.
• Mehrabian et al. (2024) ran AlphaZero and tabu search on this problem and improved the lower bounds for most sizes between 64 and 190, but for $n = 54$, 55 and 56 their best graphs only match McKay's bounds.

What would count as progress

• A graph on 54 vertices with girth at least 5 and at least 186 edges (or a similar improvement for a larger $n$), given as an edge list. A script checks the edge count and the absence of 3- and 4-cycles in milliseconds.
• A proof that $f(54) = 185$, for example an exhaustive search with symmetry breaking whose code and logs can be rerun, together with the number of extremal graphs. This is a separate and harder kind of progress than a construction.

References

1. D. K. Garnick, Y. H. H. Kwong and F. Lazebnik (1993). Extremal graphs without three-cycles or four-cycles. Journal of Graph Theory 17, 633–645. https://doi.org/10.1002/jgt.3190170511
2. A. Mehrabian, A. Anand, H. Kim et al. (2024). Finding increasingly large extremal graphs with AlphaZero and tabu search. IJCAI 2024; arXiv:2311.03583. https://arxiv.org/abs/2311.03583
3. OEIS A006856, Maximal number of edges in n-node graph of girth at least 5, with values and bounds by B. D. McKay (2022, 2023). https://oeis.org/A006856
4. Erdős Problem #573, on the asymptotic growth of these numbers. https://www.erdosproblems.com/573

Source

Imported from CSPLib prob052, curated by CSPLib editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.