2
$\begingroup$

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?

  • 0
    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.2011-10-11

1 Answers 1

1

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