Team Selection Test for IMO

Suppose that $G$ has $n$ vertices and $k$ edges and $i$-th vertex has a degree $d_i$. The number of unordered edge pairs without common vertex is equal to
$$\left(\binom{k}{2} - \sum_{i=0}^{n} \binom{d_i}{2}\right) = \frac{k(k-1)}{2} - \frac{1}{2} \sum_{i=0}^{n} d_i^2 + k = \frac{k(k+1)}{2} - \frac{1}{2} \sum_{i=0}^{n} d_i^2$$
Therefore, $\sum_{i=0}^{30} d_i^2 = 1486$. Let $\delta_i = d_i - 7$. Then $\sum_{i=0}^{30} \delta_i = 0$ and $1486 = \sum_{i=0}^{30} d_i^2 = \sum_{i=0}^{30} 7^2 + \sum_{i=0}^{30} \delta_i^2$. Therefore, $\sum_{i=0}^{30} \delta_i^2 = 16$.

Thus, $|\delta_i| \le 3$ and $d_i - d_j \le 5$. An example with $d_i = 10, d_j = 5$ can be constructed by perturbation of regular graph of degree $7$. The answer is $5$.