Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I have a weighted graph $G$, with minimum spanning tree $M$, is the following true:

If a new edge $e$ is added to $G$, in order to check whether $M$ is still the MST of $G$, it suffices to check whether the MST of $M \cup e$ is still $M$.

I concluded this after being unable to find a case where it fails. Any thoughts?

share|improve this question
    
@Srivatsan Narayanan This is true. I'm not claiming that M ∪ e is the MST, just perhaps a different configuration of the nodes in M ∪ e. –  Bill Oct 11 '11 at 20:36
    
@Srivatsan Narayanan Just need some clarification... What have you proved? I am trying to figure out whether adding a new edge to a graph will affect the MST of the graph (before the edge was added). Sorry about being confused... –  Bill Oct 11 '11 at 20:47
    
Oh my. It is not you who are confused, but I. I seem to be repeatedly misreading the question (even now, I am not very clear about what I want to show :)). I will just remove my comments and let's hope someone posts a good answer. Apologies for the inconvenience. –  Srivatsan Oct 11 '11 at 20:51

1 Answer 1

up vote 1 down vote accepted

It is true. You can use the path optimality condition for a minimum spanning tree.

Path optimality condition: Let $G$ be a connected undirected network with edge costs $c_{ij}$. Then a spanning tree $T^*$ is a minimum spanning tree if and only if, for every edge $(k,l)$ not in $T^*$, $c_{ij} \leq c_{kl}$ for every edge $(i,j)$ on the path in $T^*$ connecting nodes $k$ and $l$.

Since $M$ is an MST for $G$, we know path optimality holds for every edge in $G \cup e$ not in $M$ except possibly for $e$. Thus determining whether $M$ is an MST in $G \cup e$ is equivalent to checking path optimality for $e$. But since $e$ is the only edge in $M \cup e$ not in $M$, determining whether $M$ is an MST for $M \cup e$ is also equivalent to checking path optimality for $e$. Thus $M$ is an MST in $G \cup e$ iff $M$ is an MST in $M \cup e$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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