Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v\_1,\dots, v\_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following quantity:


$$\mathcal{I}\_k(G) := \sum\_{1\le i<j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v\_i)-\mathrm{deg}(v\_j)|\ge k}\Big\},$$
i.e. the number of all those pairs $(v\_i,v\_j)$ with degree difference greater or equal to $k$?


After some consideration, I am quite convinced that the following inequality is true:


\begin{equation} \mathcal{I}\_k(G) \ \le \ k(n-k), \end{equation}


but I am stuck on actually proving it. What can be done, we can divide $V$ into the following parts
$$A := \{v\_i : \mathrm{deg}(v\_i)\ge k\},$$
$$B := \{v\_i : \mathrm{deg}(v\_i)\le n-k\},$$
$$R=V\setminus(A\cup B).$$
Obviously, we can assume that $A$ is a clique and $B$ is an anticlique. So in the case of $|A|\ge k+1$ we get the bound directly - it is enough to erase all edges outside of $A$. The case of $|B|\ge k+1$ is similar. I am however stuck in the case of $\max(|A|, |B|)\le k$. I thought about rewriting $\mathcal{I}\_k(G)$ as
$$\mathcal{I}\_k(G) = \sum\_{i=k}^{n}|C\_i|\sum\_{j=0}^{i-k}|C\_j|,$$
where
$$C\_i := \{v\_j: \mathrm{deg}(v\_j)=i \},$$
and using some kind of degree sequence criterion, such as Erdős–Gallai and similar.


But I did not succeed. I would be very grateful for any comment or insight. Maybe looking on this question, You will think of some other related problem or theorem that might be helpful. Maybe You are able to say what a general strategy might be appropriate to handle this problem. It may turn out that for some reason this problem is trivial but I have overlooked it. I will appreciate any help or advice.



Pairs of vertices with high degree difference
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.


