# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/23.lean).

## References

1. 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](https://doi.org/10.1016/0095-8956(88)90057-3)
2. 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](https://doi.org/10.1007/978-3-030-83823-2_82); full version [arXiv:2103.14179](https://arxiv.org/abs/2103.14179)
3. 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](https://doi.org/10.1016/j.ejc.2023.103841)
4. J. Balogh, F. C. Clemen, B. Lidický, S. Norin and J. Volec, The spectrum of triangle-free graphs (2022). [arXiv:2204.00093](https://arxiv.org/abs/2204.00093)

## Source

Imported from [Erdős Problems 23](https://www.erdosproblems.com/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.