Proving the sum of length of a unique path in a tree is less than equal to $n$ choose $2$.

Question

I am having trouble on trying to prove this statement using induction. Given a tree with $n$ vertices with $n \geq 2$. $x$ is a fixed vertex, for each $v$ in the vertex set, $d(v,x)$ is the length of the unique path from $v$ to $x$ in the tree.

I know that a tree with at least $2$ vertices has at least $2$ leaves, meaning at least $2$ vertices with degree $1$. Every tree has $n - 1$ edges. If I remove $1$ leaf, I now have $n - 2$ edges. That's as far as I got. I'm not sure how to proceed. I know my goal is to reach ${k + 1 \choose 2}$.

$$\sum d(v, x) \leq {n \choose 2}$$

Answer 1

Assume that, for some integer $k\ge 2$, for all trees with $k$ vertices, for all vertex $x$ in this tree, the tree satisfy that

$$\sum_{v\in \text{vertex set of that tree}} d(v,x) \le \binom{k}{2}.$$

For the $n=k+1$ case, consider any tree with $k+1$ vertices and $k$ edges. Let $V$ be the set of all its vertices.

Pick a leaf $l\in V$ that is not the fixed vertex $x$. (Always possible as the question mentions that such tree has at least $2$ leaves.) The path length $d(l, x) \le k$, the number of edges.

Remove $l$ from the vertices, then the subtree has $k$ vertices and $k-1$ edges. By the induction hypothesis,

$$\begin{align*} \sum_{v\in V\setminus \{l\}} d(v,x) &\le \binom{k}{2}\\ \sum_{v\in V} d(v,x) &= d(l, x) + \sum_{v\in V\setminus \{l\}} d(v,x)\\ &\le k + \binom k2\\ &= \binom k1 + \binom k2\\ &= \binom{k+1}2 \end{align*}$$

Answer 2

List the vertices in order of increasing distance from $x$, that is, call the vertices $v_0,v_1,\dots,v_{n-1}$ where $d(v_0,x)\le d(v_1,x)\le\cdots\le d(v_{n-1},x)$.

Note that $d(v_0,x)=0$ since $v_0=x$, and that $$d(v_k,x)\le1+\max_{i\lt k}d(v_i,x)$$ for $0\lt k\le n-1$. It follows by induction that $d(v_i,x)\le i$ for all $i$, and $$\sum_{i=0}^{n-1}d(v_i,x)\le\sum_{i=0}^{n-1}i=\binom n2.$$

Answer 3

(Combinatorial proof, not by induction.)

Let $V$ be the vertex set of a tree with $n$ vertices, $n \ge 2$. Assign one vertex $x\in V$ to be the root of the tree. Let $S$ be the sum on the LHS in the question:

$$S = \sum_{v\in V} d(v, x).$$

Pick two distinct vertices $\{u, v\} \subseteq V$. There are two cases, depending on whether one vertex is a descendent of the other.

If neither $u$ nor $v$ is a descendent of the other, then $\{u, v\}$ contributes $0$ to the sum $S$.

Otherwise, without loss of generality, let $v$ be a descendent of $u$. Let $e$ be the edge attached to the ascendent $u$ on its path to $v$. The vertices $\{u,v\}$ identifies exactly one edge $e$ of the tree, on the path from $v$ to the root $x$. So $\{u,v\}$ contributes $1$ to $d(v,x)$, hence contributes $1$ to $S$.

There are $\binom n2$ ways to pick an unordered pair of distinct vertices from $V$, and each pair contributes at most $1$ to the sum $S$. So

$$\begin{align*}S = \sum_{v\in V} d(v,x) &= \sum_{v\in V}\text{# of ascendents of }v\\ &= \text{# of ascendent-descendent pairs}\\ &\le \text{# of unordered pairs of distinct vertices}\\ &= \binom n2. \end{align*}$$

Answer 4

If you consider the number and distances of the $n-1$ vertices other than the root, we arrive at an optimization problem:

Maximize $SP:1k_1 + 2k_2 + \dots +(n-1)k_{n-1}$, where if $k_i=0$ then if $j>i, k_j=0$, and $k_1 + k_2 + \dots + k_{n-1} = n-1$.

$k_i$ is the number of vertices at a distance of $i$ from the root.

For the induction, notice that adding another vertex raises $SP$ by at most $n$.