# maximum spanning tree

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.

• Can you please explain what you mean by a "minimum spanning tree?" – Marwan Mizuri Mar 28 '19 at 11:53
• 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 – Mohammad Farazi Mar 29 '19 at 5:25

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$$.