How to prove that height of a rooted tree is an invariant under isomorphism?

Question

Intuitively, if we're restricted to mapping the root of $T_1$ to the root of $T_2$ that makes the structure of the two trees rigid. And since under isomorphism the number of vertices are equal, height must also remain the same. But how can this be made into a formal proof? Perhaps some sort of a contradiction?

Answer 1

Like you note, the isomorphism must associate the two roots. Additionally, it sends leaves to leaves. Finally, it preserves paths; any path in $T_1$ is still a path in $T_2$, after applying the isomorphism (and vice versa). The height is just the length of the longest path from the root to a leaf; since all root-to-leaf paths in $T_1$ are isomorphic to such a path in $T_2$ of the same length, we have $h(T_1) \leq h(T_2)$; the same argument works the other way as well.