Let $G$ be a simple graph on $n$ vertices.
Prove that, for every $k\in\{2,\dots,n\}$, there exist $k$ distinct vertices in $G$ whose degrees differ by at most $k-2$.



There exist $k$ vertices with degree differences at most $k - 2$
This result was originally proved by [Erdős-Chen-Rousseau-Schelp (1993)](https://www.sciencedirect.com/science/article/pii/S0195669883710231) using the [Erdős-Gallai theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem). A more direct proof (which seems to be identical to the one in 1001's response) was given by [Caro-Lauri-Zarb (2018)](https://arxiv.org/abs/1806.08303). The latter paper appeared in Bull. Inst. Combin. Appl. 85 (2019), 79–91.


