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$ 21 Answer
$\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$
