IMC 2023 · Day 2 · P8

Hint: There are $n - 1$ pairs $u, v$ with $d(u, v) = 1$; in all other cases $d(u, v) \ge 2$.

Let $k = \binom{n}{2}$ and let $x_1 \le x_2 \le \dots \le x_k$ be the distances between the pairs of vertices in the tree $T$. Thus $$W(T) \cdot H(T) = (x_1 + x_2 + \dots + x_k) \cdot \left( \frac{1}{x_1} + \frac{1}{x_2} + \dots + \frac{1}{x_k} \right).$$ Since the tree has exactly $n - 1$ edges, there are exactly $n - 1$ pairs of vertices at distance one, that is, $x_1 = x_2 = \dots = x_{n-1} = 1$. Thus $$\begin{align*} W(T) \cdot H(T) &= (n - 1 + x_n + x_{n+1} + \dots + x_k) \cdot \left( n - 1 + \frac{1}{x_n} + \frac{1}{x_{n+1}} + \dots + \frac{1}{x_k} \right) = \\ &= (n-1)^2 + (n-1) \left( \left( x_n + \frac{1}{x_n} \right) + \dots + \left( x_k + \frac{1}{x_k} \right) \right) + {} \\ &\quad + (x_n + \dots + x_k) \left( \frac{1}{x_n} + \dots + \frac{1}{x_k} \right). \end{align*}$$ From Cauchy inequality we have $$(x_n + \dots + x_k) \left( \frac{1}{x_n} + \dots + \frac{1}{x_k} \right) \ge (1 + 1 + \dots + 1)^2 = (k - n + 1)^2 = \frac{(n-1)^2 (n-2)^2}{4}.$$ The equality holds if and only if $x_n = x_{n+1} = \dots = x_k$.

Now we minimize the expression $\left( x_n + \frac{1}{x_n} \right) + \dots + \left( x_k + \frac{1}{x_k} \right)$, where $x_i \in [2, n-1]$.

It is clear that the minimal value is achieved for $x_n = x_{n+1} = \dots = x_k = 2$. Therefore we get $$W(T) \cdot H(T) \ge (n-1)^2 + (n-1) \left( 2 + \frac12 \right) (k - n + 1) + \frac{(n-1)^2 (n-2)^2}{4} = \frac{(n-1)^3 (n+2)}{4}.$$ The equality holds for $x_1 = \dots = x_{n-1} = 1$ and $x_n = x_{n+1} = \dots = x_k = 2$, that is, the smallest value is achieved for the tree where $n - 1$ pairs are at distance one, and the remaining $k - (n-1) = \frac{(n-1)(n-2)}{2}$ pairs are at distance two. The unique tree which satisfies these conditions is the star graph $S_n$. In this case it holds $$W(S_n) \cdot H(S_n) = (n-1)^2 \cdot \frac{(n-1)(n+2)}{4} = \frac{(n-1)^3 (n+2)}{4}.$$