# Proof that "local" minimum spanning tree is "global" minimum spanning tree

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 $$|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:

"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?

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$$.
• I don't get it. The path you're talking about is a path in $T_1$. Why would there be an edge in that path, that, when added to $T_2$ would form, along with some other edges of $T_2$, a cycle containing $e$? Oct 21, 2020 at 15:02
• If I follow you, there's that edge, let's call it $f$, in $T_1$, that reconnects the two components of $T_2 \setminus \{e\}$. What proves that the fundamental cycle in $T_2$ associated to $f$ contains $e$ ? Oct 21, 2020 at 15:48
• If I remove $e = \{x, y\}$ from $T_2$, I get two connected components $T_{2, x}$, $T_{2, y}$ with $x \in T_{2, x}$ and $y \in T_{2, y}$. If I remove $e$ from the fundamental cycle it forms with edges of $T_1$, I get a path $P_1$ from $x$ to $y$ composed of edges of $T_1$. One of these edges must have one end in each component $T_{2, x}$, $T_{2, y}$ (because any path that starts in a set of vertices and ends in another set of vertices must contain an edge with one extremity in each set). I call that edge $f = \{x', y'\}$, with $x' \in T_{2, x}$ and $y' \in T_{2, y}$. Oct 21, 2020 at 19:26
• $f$ does not belong to $T_2$, otherwise, since $f$ connects $T_{2, x}$ and $T_{2, y}$, and since $f \neq e$, $T_2 \setminus \{e\}$ would be connected. Oct 21, 2020 at 19:26