# Sparse halves in triangle-free graphs

If a graph has no triangles, must some half of its vertices span few edges? Erdős and Rousseau conjectured that every triangle-free graph on $n$ vertices has a set of $\lfloor n/2\rfloor$ vertices spanning at most $n^2/50$ edges, a bound attained by blow-ups of the 5-cycle and of the Petersen graph. The constant has been improved several times but $1/50$ is still out of reach.

## Problem

Let $G$ be a graph on $n$ vertices such that every induced subgraph on at least $\lfloor n/2\rfloor$ vertices has more than $n^2/50$ edges. Must $G$ contain a triangle?

Equivalently: does every triangle-free graph on $n$ vertices contain a set of $\lfloor n/2\rfloor$ vertices that spans at most $n^2/50$ edges? Erdős offered \$250 for this problem.

## Background

The question is due to Erdős and Rousseau and is known as the sparse halves conjecture. The constant $50$ would be best possible: in the balanced blow-up of the 5-cycle, or of the Petersen graph, every half spans at least $n^2/50$ edges. Erdős, Faudree, Rousseau and Schelp (1994) proved the statement with $50$ replaced by $16$, and more generally that if every set of at least $\alpha n$ vertices spans more than $\alpha^3n^2/2$ edges, then $G$ contains a triangle. The problem is linked, through work of Brandt on eigenvalues of regular graphs, to the question of making triangle-free graphs bipartite.

## What is known

- **Weaker constants.** Krivelevich (1995) proved the analogous statement for sets of $3n/5$ vertices (with $25$ in place of $50$). Razborov (2022) proved the conjecture with $1/50$ replaced by $27/1024$.
- **Dense or sparse graphs.** Keevash and Sudakov (2006) proved the conjecture when $G$ has at most $n^2/12$ or at least $n^2/5$ edges, and Norin and Yepremyan (2015) extended this to graphs with at least $(1/5-c)n^2$ edges for some $c>0$.
- **Computation.** Searches reported on the problem's forum in 2026, over small triangle-free graphs and blow-ups of known strongly regular graphs, found no counterexample.
- **Claims.** A proof claim posted in August 2026 (A. Sarid) improves $27/1024\approx0.02637$ to $0.0262$, combining flag algebras for dense graphs with a theorem of Balogh, Clemen and Lidický for sparse ones; its Lean formalisation takes that theorem as an assumption. It has not been refereed.

## What would count as progress

- A proof of the conjecture for a new range of edge densities, or with a constant closer to $1/50$ than $27/1024$.
- A counterexample: a triangle-free graph on $n$ vertices in which every set of $\lfloor n/2\rfloor$ vertices spans more than $n^2/50$ edges; for moderate $n$ this can be verified exactly by computer.
- A formal proof against the Lean statement in [formal-conjectures](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/128.lean).

## References

1. P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, A local density condition for triangles, *Discrete Math.* 127 (1994), 153–161. [doi:10.1016/0012-365X(92)00474-6](https://doi.org/10.1016/0012-365X(92)00474-6)
2. M. Krivelevich, On the edge distribution in triangle-free graphs, *J. Combin. Theory Ser. B* 63 (1995), 245–260. [doi:10.1006/jctb.1995.1018](https://doi.org/10.1006/jctb.1995.1018)
3. P. Keevash and B. Sudakov, Sparse halves in triangle-free graphs, *J. Combin. Theory Ser. B* 96 (2006), 614–620. [doi:10.1016/j.jctb.2005.11.003](https://doi.org/10.1016/j.jctb.2005.11.003)
4. S. Norin and L. Yepremyan, Sparse halves in dense triangle-free graphs, *J. Combin. Theory Ser. B* 115 (2015), 1–25. [doi:10.1016/j.jctb.2015.04.006](https://doi.org/10.1016/j.jctb.2015.04.006)
5. A. A. Razborov, More about sparse halves in triangle-free graphs, *Sb. Math.* 213 (2022), 109–128. [doi:10.1070/SM9615](https://doi.org/10.1070/SM9615)

## Source

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