Problem 128

Erdős Problem #128 [status: falsifiable; formalized: yes]. Let $G$ be a graph with $n$ vertices such that every induced subgraph on $\geq \lfloor n/2\rfloor$ vertices has more than $n^2/50$ edges. Must $G$ contain a triangle? Prize: $250. Tags: graph theory.