A question of Erdős, Fajtlowicz, and Staton. Erdős [Er93] writes 'Perhaps very much more is true but we could not even prove this seemingly weak result'.

By Ramsey's theorem every graph on $n$ vertices contains a trivial subgraph on $\gg \log n$ many vertices.

This is true, and was proved by Prömel and Rödl [PrRo99], in the strong sense that, for any $c>0$, if $G$ contains no trivial subgraph on $\geq c\log n$ vertices then $G$ contains all graphs with $O_c(\log n)$ many vertices as induced subgraphs.

See also [82] for how large an induced regular subgraph a general graph must contain.

View the LaTeX source