I don't get the formal way of proving the following cases:

Suppose I have a minimum spanning tree $T$ in a graph $G(V, E)$, with positive edge weights $w$, I want to prove the following:

1) If I increase the edge weight of an edge that is not in $T$, then my resulting tree is still the minimum spanning tree.

This obviously makes sense since none of the edges of $T$ have been modified, and even so, the new edges will only have weights higher than $T$. Is there a way I could put this in a formal way?

2) If I decrease the edge weight of an edge that is in $T$, then my resulting tree is still the MST.

Again, this is very intuitive since the minimum weight of my MST is already the minimum, any reduced amount will still make it minimum. Again, the problem is putting this into formal proof.

3) After adding a new edge $e$ with a unique weight $w(e)$ in $G$, the tree will still be an MST.

  • $\begingroup$ Part 3) is just wrong. Even without allowing parallel edges, you can have a weighted graph $G = (V,E,w)$ where $V = \{a,b,c\}$, $E = \{(a,b),(b,c)\}$, $w(a,b) = 2$, and $w(b,c) = 3$. There's exactly one (M)ST consisting of all edges. Add the edge $(a,c)$ with the unique weight $w(a,c) = 1$ and the old MST is no longer minimal. $\endgroup$ – Kai Apr 7 '18 at 11:40

For part (1), denote by $w$ the weight of a tree in the original tree, and by $w'$ its weight in the new tree. Since $T$ is an MST, we have $w(T) \leq w(T')$ for every tree $T'$. Also, $w'(T) = w(T)$ and $w'(T') \geq w(T')$ for all $T'$. Therefore $w'(T) = w(T) \leq w(T') \leq w'(T')$ for all trees $T'$, that is, $T$ is an MST with respect to $w'$ as well.

Part (2) is similar to part (1), though slightly more challenging. Suppose that we decreased the weight on an edge in $T$ by an amount $\delta$. Then $w'(T) = w(T) - \delta$, and $w'(T') \geq w(T') - \delta$ for every tree $T'$. Therefore $w'(T) = w(T) - \delta \leq w(T') - \delta \leq w'(T')$ for every tree $T'$, and so $T$ is an MST with respect to $w'$ as well.

I couldn't quite understand part (3), but I think you've seen enough examples of how these proofs go.


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.