International Mathematics Competition
for University Students
2023

IMC2023: Day 2, Problem 8

Problem 8. Let \(\displaystyle T\) be a tree with \(\displaystyle n\) vertices; that is, a connected simple graph on \(\displaystyle n\) vertices that contains no cycle. For every pair \(\displaystyle u,v\) of vertices, let \(\displaystyle d(u,v)\) denote the distance between \(\displaystyle u\) and \(\displaystyle v\), that is, the number of edges in the shortest path in \(\displaystyle T\) that connects \(\displaystyle u\) with \(\displaystyle v\).

Consider the sums

\(\displaystyle W(T)=\sum_{\substack{\{u,v\} \subseteq V(T)\\ u\ne v}} d(u,v) \quad\text{and}\quad H(T)=\sum_{\substack{\{u,v\} \subseteq V(T)\\ u\ne v}} \frac{1}{d(u,v)}. \)

Prove that

\(\displaystyle W(T)\cdot H(T)\geq \frac{(n-1)^{3}(n+2)}{4}. \)

Slobodan Filipovski, University of Primorska, Koper

Solution. Let \(\displaystyle k=\binom{n}{2}\) and let \(\displaystyle x_{1}\leq x_{2}\leq \ldots \leq x_{k}\) be the distances between the pairs of vertices in the tree \(\displaystyle T.\) Thus

\(\displaystyle W(T)\cdot H(T)=(x_{1}+x_{2}+\ldots+x_{k})\cdot \left(\frac{1}{x_{1}}+\frac{1}{x_{2}}+\ldots+\frac{1}{x_{k}}\right).\)

Since the tree has exactly \(\displaystyle n-1\) edges, there are exactly \(\displaystyle n-1\) pairs of vertices at distance one, that is, \(\displaystyle x_{1}=x_{2}=\ldots=x_{n-1}=1.\) Thus

\(\displaystyle W(T)\cdot H(T)=(n-1+x_{n}+x_{n+1}+\ldots+x_{k})\cdot \left(n-1+\frac{1}{x_{n}}+\frac{1}{x_{n+1}}+\ldots+\frac{1}{x_{k}}\right)=\)

\(\displaystyle =(n-1)^{2}+(n-1)\left(\left(x_{n}+\frac{1}{x_{n}}\right)+\ldots+\left(x_{k}+\frac{1}{x_{k}}\right)\right)+\)

\(\displaystyle +(x_{n}+\ldots+x_{k})\left(\frac{1}{x_{n}}+\ldots+\frac{1}{x_{k}}\right).\)

From Cauchy inequality we have

\(\displaystyle (x_{n}+\ldots + x_{k})\left(\frac{1}{x_{n}}+\ldots+\frac{1}{x_{k}}\right)\geq (1+1+\ldots+1)^{2}=(k-n+1)^{2}=\frac{(n-1)^{2}(n-2)^{2}}{4}.\)

The equality holds if and only if \(\displaystyle x_{n}=x_{n+1}=\ldots=x_{k}.\)
Now we minimize the expression \(\displaystyle \left(x_{n}+\frac{1}{x_{n}}\right)+\ldots+\left(x_{k}+\frac{1}{x_{k}}\right)\), where \(\displaystyle x_{i}\in [2, n-1] .\)
It is clear that the minimal value is achieved for \(\displaystyle x_{n}=x_{n+1}=\ldots=x_{k}=2.\) Therefore we get

\(\displaystyle W(T)\cdot H(T)\geq (n-1)^2+(n-1)\left(\left(2+\frac{1}{2}\right)(k-n+1)\right)+\frac{(n-1)^{2}(n-2)^{2}}{4}=\frac{(n-1)^{3}(n+2)}{4}.\)

The equality holds for \(\displaystyle x_{1}=\ldots=x_{n-1}=1\) and \(\displaystyle x_{n}=x_{n+1}=\ldots=x_{k}=2\), that is, the smallest value is achieved for the tree where \(\displaystyle n-1\) pairs are at distance one, and the remaining \(\displaystyle 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 \(\displaystyle S_{n}.\) In this case it holds

\(\displaystyle W(S_{n})\cdot H(S_{n})=(n-1)^{2}\cdot \frac{(n-1)(n+2)}{4}=\frac{(n-1)^{3}(n+2)}{4}.\)