0
$\begingroup$

I wonder how to prove that given a Minimum Spanning Tree of a graph, the other spanning tree with the least common edge with Minimum Spanning Tree is always Maximum Spanning tree.

$\endgroup$
  • $\begingroup$ Can you please explain what you mean by a "minimum spanning tree?" $\endgroup$ – Marwan Mizuri Mar 28 at 11:53
  • 1
    $\begingroup$ A minimum spanning tree of a weighted graph is a spanning tree of that graph with minimum total possible weights. You can find it here: en.m.wikipedia.org/wiki/Minimum_spanning_tree $\endgroup$ – Mohammad Farazi Mar 29 at 5:25
1
$\begingroup$

I suppose that “the other spanning tree with the least common edge with Minimum Spanning Tree” means that if $T’$ is a spanning tree with minimum number of common edges with a given minimum spanning tree $T$. Then the claim may fail and $T’$ can be non-maximal. For instance, let $G=K_5$ be a complete graph with $n=5$ vertices. Let weight of a fixed edge $e$ of $G$ is $2$ and weights of all other edges of $G$ are $1$. Let $T$ be a spanning tree of $G$. Then $T$ is a minimum spanning tree iff $e$ is not an edge of $T$ and $T$ is a maximum spanning tree iff $e$ is an edge of $T$. To refute the claim it remains to note that there are two edge-disjoint spanning trees of $G$ not containing $e$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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