Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a connected, undirected graph $G=(V,E)$, with a weight function $w\colon E\to R$ and let $T$ be a minimum spanning tree. Now assume that we remove a particular edge $e$. The exercise is to find a minimum spanning tree to the new graph.

I've thought of an algorithm: Look at the cut determined by $T$ and $e$, and then replace $e$ by the minimal weighted edge crossing that cut (if such an edge exists). But I don't know how to prove this works. Help?

share|cite|improve this question
Clearly, if $e$ is not in $T$, then $T$ is a minimal spanning tree of $G-e$. Also, if $e$ is a cut-edge of $G$, then $G-e$ is not connected, hence no spanning tree exists. – digital-Ink Jan 14 '12 at 21:56
I agree. So the problem is reduced to the situation where e is in T, and it isn't a cut edge – Ben Berger Jan 14 '12 at 22:09
I don't know what is meant by "the cut determined by $T$ and $e$." – Gerry Myerson Jan 14 '12 at 22:49
I assume e is in T. So if I remove e from T, then two connected components are left, and they form a cut for the graph (i.e a partition of V into two subsets). That's what I meant in "the cut determined by T and e". – Ben Berger Jan 14 '12 at 22:57

Your Answer


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

Browse other questions tagged or ask your own question.