IMC 2023, Day 2, Problem 8
Let be a tree with vertices; that is, a connected simple graph on vertices that contains no cycle. For every pair of vertices, let denote the distance between and , that is, the number of edges in the shortest path in that connects with .
Consider the sums
Prove that
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
(proposed by Slobodan Filipovski, University of Primorska, Koper)
Hint: There are pairs with ; in all other cases .
Solution. Let and let be the distances between the pairs of vertices in the tree . Thus
Since the tree has exactly edges, there are exactly pairs of vertices at distance one, that is, . Thus
From Cauchy inequality we have
The equality holds if and only if .
Now we minimize the expression , where .
It is clear that the minimal value is achieved for . Therefore we get
The equality holds for and , that is, the smallest value is achieved for the tree where pairs are at distance one, and the remaining pairs are at distance two. The unique tree which satisfies these conditions is the star graph . In this case it holds
Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.