Show that the removal of one edge from a minimum spanning tree and adding to it another edge with less weight creates a contradiction

47 Views Asked by At

Question: If we have two minimum spanning trees $T$ and $T'$ s.t. the $weight(T) > weight(T')$, then why if we remove the largest weight edge from $T$ that is $e$, then we add instead the largest edge in $T'$, say it's $e'$, which is smaller $weight(e') < weight(e)$, we would get a new tree called $T''$ s.t. $weight(T'') = weight(T)+w(e'') -w(e) <weight (T)$. However, this is a contradiction.

Problem: Can you please show why there is a contradiction above please?

1

There are 1 best solutions below

1
On BEST ANSWER

$T$ is supposed to be a minimum spanning tree: $\operatorname{weight}(T)$ is supposed to be the smallest value possible for any tree.

If you construct a tree $T''$ for which $\operatorname{weight}(T'') < \operatorname{weight}(T)$, then $T$ is not actually minimum. But we assumed it was!