For a tree with $n$ nodes and root $r$, prove the sum of length of paths from each vertex to $r \leq \binom{n}{2}$

Question

Basically the title, hopefully it makes sense. If I take the sum of all the lengths of the paths from each vertex to the root, I need to prove it is $\leq \binom{n}{2}$.

I'm having a hard time coming up with a way to relate the two things. Can anyone maybe offer a suggestion on where to start?

I've tried thinking of $\binom{n}{2}$ in terms of it's algebraic formula and as well as it's meaning "Number of ways to choose 2 things from n things" but I can't seem to correlate it anyhow with the tree.

Thanks

Answer 1

HINT

With $V$ the number of vertices, the $V \choose 2$ is of course the number of pairs of vertices in the tree. Now, think of possible pairings of vertices, and how that relates to the path from each of those nodes to the root.

HINT 2

Use structural induction.