To prove that the height of the rooted tree $(T, u)$ is at most twice the height of the rooted tree $(T, v)$, we proceed as follows:

Definitions:

1. Let $h_u$ be the height of the rooted tree $(T, u)$, i.e., the longest path from $u$ to any leaf in $T$.
2. Let $h_v$ be the height of the rooted tree $(T, v)$, i.e., the longest path from $v$ to any leaf in $T$.
3. Since $T$ is a tree, there is exactly one path between any two nodes $u$ and $v$, which we denote by $P(u, v)$. Let the length of $P(u, v)$ (in terms of edges) be $d(u, v)$.

Key Observations:

• Any path from $u$ to a leaf must pass through $v$ or another node on $P(u, v)$, because $P(u, v)$ is the unique path between $u$ and $v$.

Step 1: Bound the height $h_u$ using $h_v$.

Consider the longest path from $u$ to any leaf:

1. If this path passes through $v$, its length can be expressed as the sum of two segments:
   • The segment from $u$ to $v$ (of length $d(u, v)$).
   • The segment from $v$ to a leaf, which is bounded by $h_v$, the height of the tree rooted at $v$.

Thus, the height of the tree rooted at $u$ satisfies: $h_u \leq d(u, v) + h_v$

Step 2: Bound $h_v$ using $h_u$.

Similarly, consider the longest path from $v$ to any leaf:

1. If this path passes through $u$, its length can be expressed as:
   • The segment from $v$ to $u$ (of length $d(u, v)$).
   • The segment from $u$ to a leaf, which is bounded by $h_u$.

Thus, the height of the tree rooted at $v$ satisfies: $h_v \leq d(u, v) + h_u$

Step 3: Combine the inequalities.

From Step 1: $h_u \leq d(u, v) + h_v$ From Step 2: $h_v \leq d(u, v) + h_u$

Adding these two inequalities: $h_u + h_v \leq 2d(u, v) + h_u + h_v$

Cancel $h_u + h_v$ on both sides (valid because heights are non-negative): $0 \leq 2d(u, v)$

This ensures that the relationship is valid. Specifically, observe that: $h_u \leq 2h_v$ if $d(u, v) \leq h_v$, which holds because $d(u, v)$ is the distance between two vertices in the tree, and $h_v$ accounts for all paths through $v$.

Similarly: $h_v \leq 2h_u$

Thus, the height of the tree rooted at $u$ is at most twice the height of the tree rooted at $v$.

---

Summary:

We have shown that: $h_u \leq 2h_v \quad \text{and} \quad h_v \leq 2h_u$ This implies that the height of the tree rooted at $u$ is at most twice the height of the tree rooted at $v$, and vice versa.

---

Questions:

1. How does the unique path property of trees play a role in this proof?
2. Could this result be generalized to other acyclic graphs or non-tree structures?
3. What happens if $u$ and $v$ are leaves of the tree?
4. Can we extend this result to weighted trees?
5. How would the result change if $T$ were not a tree but a general graph?

Tip:

When working with tree properties, leveraging the unique path between any two nodes simplifies the analysis and helps establish