Making a triangle-free graph bipartite

A triangle-free graph need not be bipartite, but how far from bipartite can it be? Erdős conjectured that a triangle-free graph on $5n$ vertices can always be made bipartite by deleting at most $n^2$ edges, the number needed for a balanced blow-up of the 5-cycle. Any graph that needs more deletions would be a counterexample, which makes the problem a natural target for computer search.

Problem

Let $G$ be a triangle-free graph on $5n$ vertices. Can $G$ always be made bipartite by deleting at most $n^2$ edges?

Equivalently, does every triangle-free graph on $N$ vertices have a cut containing all but at most $N^2/25$ of its edges?

Background

The bound would be best possible: blow up each vertex of a 5-cycle into an independent set of $n$ vertices, joining two sets completely when the original vertices are adjacent. The resulting graph is triangle-free, has $5n^2$ edges, and one must delete at least $n^2$ of them to make it bipartite. Erdős posed the question repeatedly from 1969 onwards, and Erdős, Faudree, Pach and Spencer (1988) studied it in "How to make a graph bipartite". In 1992 Erdős asked more generally whether a graph on $(2k+1)n$ vertices in which every odd cycle has length at least $2k+1$ can be made bipartite by deleting at most $n^2$ edges.

What is known

Best bound. Erdős, Faudree, Pach and Spencer showed that $N^2/18$ deletions suffice for a triangle-free graph on $N$ vertices. Balogh, Clemen and Lidický (2021) improved this to $N^2/23.5$ , that is, at most about $1.064\,n^2$ edges when $N=5n$ .
Dense and sparse graphs. The same authors proved the conjecture for graphs with edge density at most $0.2486$ and for graphs with edge density at least $0.3197$ ; the open range lies in between.
A spectral special case. Brandt conjectured in 1997 that the smallest eigenvalue $q_n(G)$ of the signless Laplacian of a regular triangle-free graph on $n$ vertices is at most $4n/25$ , a statement implied both by this conjecture and by the sparse-halves conjecture of Erdős and Rousseau. Balogh, Clemen, Lidický, Norin and Volec proved the stronger bound $q_n(G)\le 15n/94$ for all triangle-free graphs. A survey of Balogh, Clemen and Lidický (2024) collects ten open problems on partitions of triangle-free graphs.

What would count as progress

A counterexample: a triangle-free graph on $5n$ vertices whose largest bipartite subgraph misses more than $n^2$ edges. For moderate $n$ this can be certified by computing a maximum cut exactly.
A smaller constant than $1.064$ in the general bound, with a verifiable certificate if the proof is computer-assisted.
A proof of the conjecture for restricted classes, such as regular or vertex-transitive triangle-free graphs.
A formal proof against the Lean statement in formal-conjectures.

References

P. Erdős, R. Faudree, J. Pach and J. Spencer, How to make a graph bipartite, J. Combin. Theory Ser. B 45 (1988), 86–98. doi:10.1016/0095-8956(88)90057-3
J. Balogh, F. C. Clemen and B. Lidický, Max cuts in triangle-free graphs, in Extended Abstracts EuroComb 2021, Trends in Mathematics, Springer (2021), 509–514. doi:10.1007/978-3-030-83823-2_82; full version arXiv:2103.14179
J. Balogh, F. C. Clemen and B. Lidický, 10 problems for partitions of triangle-free graphs, European J. Combin. 121 (2024), 103841. doi:10.1016/j.ejc.2023.103841
J. Balogh, F. C. Clemen, B. Lidický, S. Norin and J. Volec, The spectrum of triangle-free graphs (2022). arXiv:2204.00093

Source

Imported from Erdős Problems 23, curated by Thomas Bloom. 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.