PROVED
This has been solved in the affirmative.
If $G$ is a graph on $n$ vertices which contains no complete graph or independent set on $\gg \log n$ vertices then $G$ contains an induced subgraph on $\gg n$ vertices which contains $\gg n^{1/2}$ distinct degrees.
A problem of Erdős, Faudree, and Sós.
This was proved by Bukh and Sudakov
[BuSu07].
Jenssen, Keevash, Long, and Yepremyan
[JKLY20] have proved that there must exist an induced subgraph which contains $\gg n^{2/3}$ distinct degrees (with no restriction on the number of vertices).
View the LaTeX source
Additional thanks to: Zach Hunter
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #637, https://www.erdosproblems.com/637, accessed 2026-01-16
