<p>Yes. More generally, any spanning tree can be reached from any arbitrarily-chosen MST by a sequence of single-edge replacement operations that never decrease the weight. When such a sequence is used to reach another MST, it can also never increase the weight, because then it would have to decrease it at some other step. See e.g.</p>

<p>H.N. Gabow, Two Algorithms for Generating Weighted Spanning Trees in Order, SIAM J. Comput. 6, 1977, 139–150. <a href="http://epubs.siam.org/doi/pdf/10.1137/0206011" rel="nofollow noreferrer">http://epubs.siam.org/doi/pdf/10.1137/0206011</a></p>

CC BY-SA 3.0
2017-12-19T20:14:40.310Z
2017-12-19T20:14:40.310Z
David Eppstein
<p>Suppose we have an undirected connected graph $G=(V,E)$ that has several minimum spanning trees. We say two trees $T_1, T_2$ are connected if they share exactly $|V|-2$ edges(*).  In other words $T_1$ can be obtained from $T_2$ by removing exactly one edge $e_1$, and adding another edge $e_2$. </p>

<p>Now suppose we draw a new graph $H$ that its vertices are the MSTs of the graph $G$, and there is an edge between them if they share $|V|-2$ edges. The question is, is graph $H$ connected?  </p>

<p>One can view the problem also this way: can we obtain other minimum spanning trees by greedily looking for edges that can be replaced with another edge, without increasing the total weight along the way? </p>

<p>(*) Given that trees have $|V|-1$ edges, two distinct trees cannot have more than $|V|-2$ in common. So this is the maximum number of edges in common they can have. </p>

CC BY-SA 3.0
2017-12-19T17:19:21.367Z
I don't think this is a research level question.
Sasho Nikolov
CC BY-SA 3.0
2017-12-19T19:19:57.190Z
This very much looks like a research-level question to me, very similar to asking if the graph of pythagorean triples is connected or for finding an algorithm producing the $k$-perms of an $n$ set with a single change per iteration, both of which are open problems, iirc
JimN
<graph-theory><spanning-tree>
Are equally weighted MSTs closely related?
AmeerJ
# Are equally weighted MSTs closely related?

(Asked by: username_0 on 2017-12-19)

Suppose we have an undirected connected graph $G=(V,E)$ that has several minimum spanning trees. We say two trees $T\_1, T\_2$ are connected if they share exactly $|V|-2$ edges(\*). In other words $T\_1$ can be obtained from $T\_2$ by removing exactly one edge $e\_1$, and adding another edge $e\_2$.

Now suppose we draw a new graph $H$ that its vertices are the MSTs of the graph $G$, and there is an edge between them if they share $|V|-2$ edges. The question is, is graph $H$ connected?

One can view the problem also this way: can we obtain other minimum spanning trees by greedily looking for edges that can be replaced with another edge, without increasing the total weight along the way?

(\*) Given that trees have $|V|-1$ edges, two distinct trees cannot have more than $|V|-2$ in common. So this is the maximum number of edges in common they can have.

**Tags:** graph-theory, spanning-tree
> **Comments:**
> **username_1**: I don't think this is a research level question.  
> **username_2**: This very much looks like a research-level question to me, very similar to asking if the graph of pythagorean triples is connected or for finding an algorithm producing the $k$-perms of an $n$ set with a single change per iteration, both of which are open problems, iirc  

---

## 1 answers

### Answer by username_3 on 2017-12-19. Score: 4 | Accepted answer

Yes. More generally, any spanning tree can be reached from any arbitrarily-chosen MST by a sequence of single-edge replacement operations that never decrease the weight. When such a sequence is used to reach another MST, it can also never increase the weight, because then it would have to decrease it at some other step. See e.g.

H.N. Gabow, Two Algorithms for Generating Weighted Spanning Trees in Order, SIAM J. Comput. 6, 1977, 139–150. <http://epubs.siam.org/doi/pdf/10.1137/0206011>


---

