Return to Answer

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.

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): \ |\mathrm{deg}(u)-\mathrm{deg}(v)|\ge k \ \text{for some} \ u \in A \ \},$$ $$\mathrm{sp}_B = \{ v\in \mathrm{sp}(G,k-1): \ |\mathrm{deg}(u)-\mathrm{deg}(v)|\ge k \ \text{for some} \ u \in B \ \},$$ $$\mathrm{sp}_A \cap \mathrm{sp}_B = \emptyset.$$ 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.

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-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.

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.

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-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)= ab+a(k+1),$$ and as $a\le n-k-1 \le k+1$, we get $$ab+ak\le (a+b)k\le (n-k-1)(k+1), $$ which ends the proof.

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-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.