# Minimum number of edges to remove from a graph, so that MST contains a certain edge

Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $$e$$ to be in the MST. For doing so, we are allowed to remove some edges from the graph. But I don't want to remove too many edges. Is there an efficient algorithm that can find the minimum number of edges to remove before $$e$$ becomes a member of MST?

I am particularly interested in that minimum value, and not the edges to remove.

I think there is a way to find a spanning tree that contains $$e$$. All we have to do is to insert a dummy node between the two nodes that are connected by $$e$$. But I doubt this helps. Any hint would be appreciated.

• Do you want to make sure that $e$ is in all or in some MST? Jan 14 at 12:30
• @PålGD just some MST would do it. Jan 14 at 12:42
• Which property must $e$ have to never be in any MST? Jan 14 at 12:43
• It must be the heaviest edge in some cycle. Am I right? @PålGD Jan 14 at 12:47

An edge $$uv$$ is in some MST if and only if it is a minimum-weight edge of some cut. So we need to find a $$uv$$-cut with a minimum number of edges whose weight is strictly less than $$w(uv)$$. Once those edges are removed, $$uv$$ will be in some MST.
Algorithmically, any min $$st$$-cut algorithm, applied on the subgraph of edges of weight less than $$w(uv)$$, will give us the answer. For instance you can use a max $$uv$$-flow algorithm to find the cut, if you don't know fancier algorithms.
• $K_{3,2}$ is a counter-example if you let one of the degree-2 vertices have both its edges weight 2 and the remaining edges have weight 1. Let $e=uv$ be an edge with weight 2. A minimum $uv$-cut is now for example edges with weight $2,1,1$. However, $e$ is actually already in an MST. Jan 14 at 14:29
• No, if $v$ is the degree-2 vertex whose incident edges have weight 2, the min $uv$-cut is $\delta(v)$, which is empty, in the graph of edges with weight $< 2$. Jan 14 at 16:17