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 and Key Facts

1. Tree Definition: A tree is an acyclic connected graph.
2. Height of a Rooted Tree: The height of a rooted tree $(T, r)$ is the maximum distance from the root $r$ to any other node in the tree.
3. Distances in a Tree: In a tree, the distance between any two nodes $x$ and $y$, denoted $d(x, y)$, is the length of the unique path between them.

Let the height of $(T, u)$ be $h_u$ and the height of $(T, v)$ be $h_v$.

Argument

1. Re-rooting the Tree: When a tree is rooted at a node $u$, the height is determined by the maximum distance from $u$ to any other node $w \in V$, i.e., $h_u = \max_{w \in V} d(u, w)$. Similarly, $h_v = \max_{w \in V} d(v, w)$.

2. Key Idea: The distances in a tree satisfy the triangle inequality: $d(u, w) \leq d(u, v) + d(v, w).$ Similarly, reversing the roles of $u$ and $v$: $d(v, w) \leq d(v, u) + d(u, w).$

3. Bounding $h_u$:

   • For any $w \in V$, the distance from $u$ to $w$ satisfies: $d(u, w) \leq d(u, v) + d(v, w).$
   • Taking the maximum over all $w \in V$ to compute the height $h_u$: $h_u = \max_{w \in V} d(u, w) \leq d(u, v) + \max_{w \in V} d(v, w).$
   • Hence: $h_u \leq d(u, v) + h_v.$

4. Bounding $h_v$:

   • Similarly, for any $w \in V$, the distance from $v$ to $w$ satisfies: $d(v, w) \leq d(v, u) + d(u, w).$
   • Taking the maximum over all $w \in V$ to compute the height $h_v$: $h_v = \max_{w \in V} d(v, w) \leq d(v, u) + \max_{w \in V} d(u, w).$
   • Hence: $h_v \leq d(v, u) + h_u.$

5. Relating the Heights:

   • From the bounds above: $h_u \leq d(u, v) + h_v \quad \text{and} \quad h_v \leq d(v, u) + h_u.$
   • Since $d(u, v) = d(v, u)$, combining these inequalities: $h_u \leq h_v + d(u, v) \quad \text{and} \quad h_v \leq h_u + d(u, v).$
   • Adding these two inequalities: $h_u + h_v \leq 2h_v + 2d(u, v).$
   • Simplify to find: $h_u \leq 2h_v.$

Conclusion

The height of the rooted tree $(T, u)$ is at most twice the height of the rooted tree $(T, v)$: $h_u \leq 2h_v.$

This completes the proof.

---

Do you want additional details or have any questions about this proof? Here are some related questions to explore:

1. What are some examples of trees where the height inequality is tight (i.e., $h_u = 2h_v$)?
2. How does re-rooting affect the diameter of a tree?
3. Can we generalize this result to graphs that are not trees?
4. What is the significance of the triangle inequality in proving properties of trees?
5. How does this result relate to the concept of eccentricity in graph theory?

Tip: When proving inequalities in graph theory, carefully use properties like the triangle inequality and uniqueness of paths in trees