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(\left(\genfrac{}{}{0ex}{}{k}{2}\right)-\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)\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$.