# Minimum spanning tree assumption

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?

-
@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

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