# Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]

I'm pracitcing exams towards finals,

Given an undirected graph $$G(V,E)$$ , we denote 2 MST $$T,T'$$ neighbours if by deleting one edge from $$T$$ and add another one we get $$T'$$.

Prove : for every 2 distinct MST $$T,T'$$ there is a sequence of $$k$$ MST's such that every 2 MST's $$T_i,T_i+1$$(+1 on the index) in the list are neighbours and at the end of the sequence we get $$T$$

$$T' = T_1,T_2,T_3,\ldots,T_k=T$$

hope to get help.

This is a generalization of the Uniqueness property of minimum spanning trees, and the proof is almost the same:

1. Note there is at least one edge that belongs to exactly one of $$T$$ and $$T'$$. Among such edges, let $$e_1$$ be the one with least weight. Without loss of generality, assume $$e_1 \in T$$.

2. As $$T'$$ is an MST, $$e_1\cup T'$$ must contain a cycle $$C$$ with $$e_1$$.

3. As a tree, $$T$$ contains no cycles, therefore $$C$$ must have an edge $$e_2\notin T$$.

4. Since $$e_1$$ was chosen as the lowest-weight edge among those belonging to exactly one of $$T$$ and $$T'$$, the weight of $$e_2$$ must be no less than the weight of $$e_1$$.

5. As $$e_1$$ and $$e_2$$ are part of the cycle $$C$$, replacing $$e_2$$ with $$e_1$$ in $$T'$$ therefore yields a spanning tree $$T''$$ with no larger weight, thus also a minimum spanning tree. Since $$e_1\in T$$ and $$e_2\notin T$$, $$T''$$ is more "closer" to $$T$$ than $$T'$$.

6. Repeat the processes above for $$T$$ and $$T''$$. Finally you will get a sequence of mimimum spanning trees between $$T$$ and $$T'$$.