Proof that "local" minimum spanning tree is "global" minimum spanning tree I'm trying to understand a proof from the book &quot;Graph Theory with Application to Engineering &amp; Computer Science&quot; by Narsingh Deo.
The chapter is about trees in non oriented graphs.
A bit of terminology so that you can understand the theorem and the beginning of the proof from the book:
The author calls minimum spanning trees, shortest spanning trees.
The author calls a branch of a spanning tree any edge of the tree.
A chord of a spanning tree is any edge of the underlying graph that is not in the tree.
A fundamental circuit associated to a spanning tree is a circuit formed by adding one of its chords to a spanning tree (for the author a &quot;circuit&quot; is a closed path, there is no repetition of vertices, it's what most other sources I've read call a cycle). So, a fundamental circuit associated to a spanning tree is a actually a cycle formed by adding one of its chords to a spanning tree.
The distance between two spanning trees $S$ and $T$ of the same graph is (regarding $S$ and $T$ as sets of edges), is $|S\setminus T|$ (which happens to be equal to $|T\setminus S|$).
There's a step in the proof of Theorem 3-16 that I don't understand.
Theorem 3-16:
A spanning tree T (of a given weighted connected Graph G) is a shortest spanning tree (of G) if and only if there exists no other spanning tree (of G) at a distance of one from T whose weight  is smaller than that of T
Proof:
Let $T_1$ be a spanning tree in G satisfying the hypothesis of the theorem (i.e. there is no spanning tree at a distance of one from $T_1$ which is shorter than $T_1$). The proof will be completed by showing that if $T_2$ is a shortest spanning tree (different from $T_1$) in G, the weight of $T_1$ will also be equal to that of $T_2$. Let $T_2$ be a shortest spanning tree in G. Clearly, $T_2$ must also satisfy the hypothesis of the theorem (otherwise there will be a spanning tree shorter than $T_2$ at a distance of one from $T_2$, violating the assumption that $T_2$ is shortest).
Consider an edge $e$ in $T_2$ which is not in $T_1$. Adding $e$ to $T_1$ forms a fundamental circuit with branches in $T_1$. Some, but not all, of the branches in $T_1$ that form the fundamental circuit with $e$ may also be in $T_2$; each of these branches in $T_1$ has a weight smaller than or equal to that of $e$, because of the assumption on $T_1$. Amongst all those edges in this circuit which are not in $T_2$ at least one, say $b_j$, must form some fundamental circuit (with respect to $T_2$) containing $e$.
I'm stuck at the last sentence I just quoted:
&quot;Amongst all those edges in this circuit which are not in $T_2$ at least one, say $b_j$, must form some fundamental circuit (with respect to $T_2$) containing $e$.&quot;
I don't see why among those cycles, there should necessarily be one that contains $e$. Why is that?
If we remove $e = (x,y)$ from $T_2$, then it breaks into two connected components, say $T_{2,x},T_{2,y}$. There is a unique path in $T_1$ from $x$ to $y$, which together with $e$ forms a fundamental cycle of $T_1$. The path starts at $T_{2,x}$ and ends at $T_{2,y}$, hence at some point it crosses between the two. Adding the corresponding edge to $T_2$ would result in a fundamental cycle containing $e$.