I have just found out a very similar theorem to the one in the question. Some work still must be done, but it seems clear that it is very closely related. https://arxiv.org/pdf/1806.08303.pdf Let $G = (V, E)$ be a simple graph. For $B$ a subset of the vertex set $V$ , we define the spread of $B$ as $$\mathrm{sp}(B) = \Big\{\max[\mathrm{deg}(u)]− \min[\mathrm{deg}(v)] : u, v ∈ B\Big\}.$$ We then define, for an integer $k ≥ 0$, quantity $\mathrm{sp}(G, k)$ as: $$\max{\Big\{|B|: \ {sp(B) ≤ k}\Big\}},$$ i.e. "the largest cardinality of a subset of vertices of $G$ with spread at most $k$". Now, we have the following, **Theorem** (*Erdős, Chen, Rousseau and Schelp*): > Let $G$ be a graph on $n ≥ k+1$ vertices, then $\mathrm{sp}(G, k-1) ≥ k + 1.$ EDIT: I think that this indeed answers the question. Let $m$ be the minimal degree of $\mathrm{sp}(G,k-1)$, and let $M$ be the maximal. Define $$A:=\{v_i : \mathrm{deg}(v_i)<m\},$$ $$B:=\{v_j: \mathrm{deg}(v_j)>M\}.$$ Set $a=|A|, b=|B|$. We know that $a+b<n-k$. Now, take a vertex $v\in \mathrm{sp}(G, k-1)$ and observe that $v$ cannot be connected with a vertex in $A$ and $B$ simultaneously. Thus we can define $$\mathrm{sp}_A = \{ v\in \mathrm{sp}(G,k-1): \ vu\in E \ \text{for some} \ u \in A \ \},$$ $$\mathrm{sp}_B = \{ v\in \mathrm{sp}(G,k-1): \ vu\in E \ \text{for some} \ u \in B \ \}.$$ Set $x_1=|\mathrm{sp}_A|, x_2=|\mathrm{sp}_B|$. Thus $$a+b\le n-k,$$ $$x_1+x_2\le k,$$ and we have $$\mathcal{I}_k(n)\le ab+ax_1+bx_2 \le (a+b)(x_1+x_2) \le k(n-k),$$ which ends the proof.