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

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

  Solution