To prove that the height of the rooted tree $(T, u)$ is at most twice the height of the rooted tree $(T, v)$, we analyze the structure of trees and the properties of paths between nodes. Here’s the detailed reasoning:

---

Key Definitions and Observations

1. Tree and Height:

   • A tree is a connected acyclic graph.
   • The height of a rooted tree $(T, r)$ is the maximum distance (in terms of edges) from the root $r$ to any other node in the tree.

2. Path Property in Trees:

   • In a tree, there is a unique simple path between any two nodes.

3. Relocation of Root:

   • When changing the root of a tree from $v$ to $u$, the height of the tree changes depending on the relative positions of $u$ and $v$ and the distance between them.

---

Proof

1. Let $h_v$ and $h_u$ denote the heights of the rooted trees $(T, v)$ and $(T, u)$, respectively.

2. Consider any node $x \in V$. The distance from $x$ to $u$ (when $u$ is the root) can be expressed as: $d(u, x) = d(v, x) + d(v, u),$ or $d(u, x) = |d(v, x) - d(v, u)|.$

   The above equation reflects that the distance to $u$ is adjusted by the distance between $u$ and $v$, depending on whether $x$ is "closer to" $v$ or not.

3. Height Adjustment:

   • When changing the root from $v$ to $u$, the maximum distance $d(u, x)$ for any $x \in V$ can at most double:
     • The farthest point from $u$ must lie either in the subtree rooted at $v$ or in the opposite direction of $v$ (relative to $u$).
     • The farthest node in the direction of $v$ contributes approximately $h_v + d(u, v)$ to the height of $(T, u)$.
     • In the opposite direction, a similar argument shows that no path can exceed $2h_v$.

4. Thus, the new height satisfies: $h_u \leq 2h_v.$

---

Why Not $n$-times?

The height cannot grow $n$-times because:

• The height of a tree is inherently limited by the longest path (diameter) of the tree.
• Moving the root cannot introduce new nodes or paths but only redistributes how distances are measured.
• The doubling effect is a result of the longest path being recalculated with the new root and does not grow arbitrarily.

---

Conclusion

The height of the rooted tree $(T, u)$ is at most twice the height of the rooted tree $(T, v)$ because relocating the root at most doubles the longest path from the root to the farthest leaf.

---

Do you want further clarification or a diagram to explain this concept?

---

5 Related Questions:

1. How does the diameter of a tree relate to its height under different roots?
2. Can the height of a tree decrease when moving the root? If so, under what conditions?
3. What happens to the height when the tree is a star graph with $n$ nodes?
4. How does this property generalize to unrooted graphs?
5. What is the relationship between the center and centroid of a tree in terms of height?

---

Tip:

To fully understand height changes in rooted trees, visualize paths and the impact of shifting roots using simple tree structures