# Are equally weighted MSTs closely related?

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.

• I don't think this is a research level question. Dec 19 '17 at 17:19
• 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
Dec 19 '17 at 19:19