I’m trying to understand a proof from the book “Graph Theory with Application to Engineering & Computer Science” 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 “circuit” 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 $|Ssetminus T|$ (which happens to be equal to $|Tsetminus S|$).
There’s a step in the proof of Theorem 3-16 that I don’t understand.
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
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:
“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 don’t see why among those cycles, there should necessarily be one that contains $e$. Why is that?