Large Induced Subgraphs with $k$ Vertices of Almost Maximum Degree

In this note, we prove that for every integer $k$, there exist constants $g_{1}(k)$ and $g_{2}(k)$ such that the following holds. If $G$ is a graph on $n$ vertices with maximum degree $\Delta$ then it contains an induced subgraph $H$ on at least $n - g_{1}(k)\sqrt{\Delta}$ vertices, such that $H$ contains $k$ vertices of the same degree of order at least $\Delta(H)-g_{2}(k)$. This solves an approximate version of a conjecture of Caro and Yuster which states that $g_2(k)$ can be taken to be $0$ for every $k$. Note that in our result we allow the common degree to be at most an additive constant far from the maximum degree.