International Mathematics Competition
for University Students
2023

Select Year:


IMC 2024
Information
  Schedule
  Problems & Solutions
  Results
  Contact
 

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\).

    

IMC
2023

© IMC