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-1$.
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-1,$$ $$x_1+x_2\le k+1,$$
and we have
$$\mathcal{I}_k(G)\le ab+ax_1+bx_2.$$
We can further assume that $a\ge b$, thus:
$$ab+ax_1+bx_2 \le ab+a(x_1+x_2)\le ab+a(k+1),$$
and as $a\le n-k-1 \le k+1$, we get
$$ab+a(k+1)\le (a+b)(k+1)\le (n-k-1)(k+1), $$
which ends the proof.