Logo
All Random Solved Random Open
OPEN
Let $\epsilon>0$ and $n$ be large. Let $G$ be a graph on $n$ vertices containing no $K_5$ and such that every set of $\epsilon n$ vertices contains a triangle. Must $G$ have $o(n^2)$ many edges?
The best known result is that $G$ can have at most $(\tfrac{1}{12}+o(1))n^2$ many edges.

See also the entry in the graphs problem collection.