I am trying to prove the above statement. This Lemma popped up when I am studying Prim's Algorithm.
The proof given in the book (Baase & Van Gelder P392) is by Induction:
Let $k$ be the number of edges in $T1$ but not in $T2$ (and Vice Versa).
Base Case: $k=0$, $T1 = T2$, hence they have the same weight.
Inductive Step: For $k>0$, Assume the Lemma holds when there are $j$ differing edges where $0 < j < k$. Let $uv$ be the minimum weight edge among the differing edges (assume $uv$ in $T2$).
Look at the unique path in T1 from $u$ to $v$. Suppose that it is made up of $w0$...$wp$ where $w0 = u, wp = v$. This path must contain some edge different from T2.
This is part of the proof only, but I am currently stuck at the last statement where "This path must contain...".
I'm thinking in the direction where if T2 does not have different edges, then it contains this path. But I still find it hard to wrap my head around about how does it connect to the proof.
Thanks for your time!
This is a somewhat standard argument involving edges which are not in trees. By assumption you have $uv$ in $T_2$. The unique path $p$ in $T_1$, which connects $u$ and $v$ does not contain $uv$ by assumption. So if this whole path $p$ was contained in $T_2$, you'd have two different paths in $T_2$ connecting $u$ and $v$, namely the single edge $uv$ and the path $p$.
But that means that $T_2$ contains a circle, which contradicts $T_2$ being a tree. Hence not all of $p$ can be contained in $T_2$, thus there must exist some edge in $p$ which is not in $T_2$.