2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't think this is a research level question. $\endgroup$
    – Sasho Nikolov
    Commented Dec 19, 2017 at 17:19
  • 1
    $\begingroup$ 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 $\endgroup$
    – JimN
    Commented Dec 19, 2017 at 19:19

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.