Ukrainian National Mathematical Olympiad

Show that:
$$d + \frac{D}{n-1} \le \frac{1}{2}(n+1)(n+2).$$

Let $i \ne j$, and let the shortest path between $A_i$ and $A_j$ be the following: $A_i = A_{\gamma_0}, A_{\gamma_1}, \dots, A_{\gamma_k} = A_j$. Let $X$ be the set of such vertices ($k+1$ vertices), and let $Y$ be the set of all other vertices ($n-k-1$ vertices total). The number of edges that connects vertices inside $Y$ is not greater than $C_{n-k-1}^2$. All edges that connect vertices inside $X$ are the edges of the shortest path, otherwise there exists shorter path between $A_i$ and $A_j$. Therefore, there are exactly $k$ edges.

If $A \in Y$, then there are 3 or less edges that connect $A$ with vertices from $X$. Otherwise, there exists shorter path than the one that has $k$ edges. Therefore, there exists not more than $3(n-k-1)$ edges that connect vertices from $X$ and vertices from $Y$. Thus,
$$\begin{aligned} d \le C_{n-k-1}^2 + k + 3(n-k-1) &= \frac{1}{2}(n^2 + 3n - 4 + k^2 - k - 2kn) \le \\ & \quad (k < n, \text{ hence } kn < n^2) \\ \le \frac{1}{2}(n^2 + 3n - 4) - \frac{n+1}{2}k &\Rightarrow d + \frac{n+1}{2}d_{i,j} \le \frac{1}{2}(n^2 + 3n - 4), \text{ thus} \\ \sum_{1 \le i < j \le n} \left(d + \frac{n+1}{2}d_{i,j}\right) &\le \frac{1}{2}C_n^2(n^2 + 3n - 4), \text{ so} \\ C_n^2d + \frac{n+1}{2}D &\le \frac{1}{2}C_n^2(n^2 + 3n - 4). \end{aligned}$$

The given inequality can be obtained by dividing inequality by $C_n^2$ and using
$$\frac{n+1}{n(n-1)} \ge \frac{1}{n-1} \quad \text{and} \quad n^2 + 3n - 4 \le n^2 + 3n + 2.$$