Logo
All Random Solved Random Open
OPEN - $250
Let $G$ be a graph with $n$ vertices such that every subgraph on $\geq n/2$ vertices has more than $n^2/50$ edges. Must $G$ contain a triangle?
A problem of Erdős and Rousseau. The constant $50$ would be best possible as witnessed by a blow-up of $C_5$ or the Petersen graph. Krivelevich [Kr95] has proved this with $n/2$ replaced by $3n/5$ (and $50$ replaced by $25$).

Keevash and Sudakov [KeSu06] have proved this under the additional assumption that $G$ has at most $n^2/12$ edges.

See also the entry in the graphs problem collection.

Additional thanks to: Boris Alexeev