# What edges are not in any MST?

This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed.

Consider a weighted undirected graph. What edges of it are not a part of any minimum spanning tree (MST)? This problem only makes sense when several edges have the same weight, otherwise the MST is unique.

My idea comes from Prim's Algorithm with a slight change. Let $S$ and $T$ be two sets of vertices the algorithm works with. Instead of adding the minimum edge from $S$ to $T$ on every step, look for the minimum edge and more edges of the same value going from $S$ to the vertex the minimum edge goes to. By doing that, (so I suppose) we will obtain a graph containing all the edges which appear in any MST. If this is right, I can simply XOR the edges list with the original graph edges list to find what edges are not in any MST.

• I think the question is probably meant to be more conceptual and less algorithmic. Here's a hint: What if I gave you a graph with $n$ edges (that is, a spanning tree with one edge that doesn't belong in it). How would you know which is the edge that doesn't belong? – Joe Dec 10 '12 at 23:19
• Thanks Joe, I obviously meant a weighted graph (fixed that). About your hint: for example a graph with 3 vertex and 3 edges, fully connected with every edge weighing 2. Every edge is in at least one MST. – The-Q Dec 11 '12 at 5:46
• How is the question exactly phrased. I was expecting something like "the unique maximal edge is not in any MST" as an answer. – A.Schulz Dec 11 '12 at 7:31
• This sounds like one of those questions that only make sense if you know what the questioner is thinking. If the question was "what is a case where an edge can never be part of a MST", I can think of a good answer. (Hint: Think of a triangle.) – usul Dec 11 '12 at 7:51
• Hey and thank you for your comments. The original question is "Find an algorithm which returns what edges are not in any possible MST for a given undirected, weighted graph". The algorithm I stated in the original question has already been found wrong. – The-Q Dec 11 '12 at 22:29

A Google search for "edges not in MST" leads me to this question. The answer included in the question has already been found wrong, as OP said in the last comment. For future references, here is my solution to the question.

Let $$G$$ be a weighted undirected (finite) graph. An edge $$e$$ is called superheavy if it is the unique heaviest edge in some cycle. Here is a characterization of the edges that are not in any MST.

## An edge is not in any MST if and only if it is a superheavy edge

The well-known "if" part, a superheavy edge is not in any MST, is proved in the cycle property of MST.

The "only if" part, any edge $$e$$ that is not superheavy is in some MST, is harder to prove. Let me introduce an algorithm and a lemma first.

The delete-heaviest-edge algorithm (DHE) on $$G$$ removes a heaviest edge in any cycle until no cycle remains. Just to be extra clear, there might be multiple heaviest edges in one cycle. The edge removed can be chosen to be any one of them.

Lemma: DHE is an MST algorithm. That is, the final graph at the end of DHE is an MST of the original $$G$$.

One proof of the lemma can be developed by adapting the proof at reverse-delete algorithm.

For another proof of the lemma, reader can check my post at the delete-heaviest-edge algorithm on graphs with edges of distinct weights, where I proved the special case where all weights are distinct. For the general case of a given run of DHE where all weights of $$G$$ are not necessarily distinct, we can perturb the weights of all edges of $$G$$ so that all weights are distinct and that each edge removed is the unique heaviest edge in the corresponding cycle. We can then repeat the given run of DHE on the perturbed $$G$$, resulting in the same spanning tree, which is also the MST of the perturbed $$G$$, since this is the proven special case of distinct weights. By making the perturbation arbitrarily small, we can see the total weight of the resulting MST can be arbitrarily near to the weight of a (or any) MST of the original $$G$$. Once we take the limit of perturbation going to $$0$$, we can see that original given run of the DHE must produce a spanning tree with the minimal weight. The lemma is proved.

Now let us prove the "only if" part. Suppose edge $$e$$ is not a superheavy edge. Let us start a particular run of DHE. We will adjust that run whenever necessary to avoid deleting $$e$$. Suppose $$e$$, as a heaviest edge in some cycle is removed in some step. Because $$e$$ is not superheavy, there is another heaviest edge, say $$f$$, in that cycle. Let us modify that step so that it removes $$f$$ instead of $$e$$. Continue to run the algorithm, alway avoiding removing $$e$$ as we just did. At the end of the algorithm, we must arrive at an MST thanks to the lemma, which contains $$e$$. Proof of the "only if" part is done.

Since an edge not in any MST means it is superheavy, any algorithm that finds all the superheavy edges will also finds all edges that are not in any MST.

## Algorithms to find all superheavy edges

Here is a naive algorithm. Iterate over all edges. For each edge $$e$$, pick arbitrarily one of its two vertices. Starting from this chosen vertex, make a DFS or BFS along edges with weight lower than that of $$e$$, checking whether we have reached the other vertex of $$e$$ all along. Once we have, $$e$$ is superheavy. Otherwise we cannot at the end of the search, implying $$e$$ is not superheavy.

It often happens that there is a unique MST, for example when all edge-weights are distinct. We can use various algorithms such as Kruskal's algorithm or Prim's algorithm to compute that unique MST. The superheavy edges are the edges that are not in that unique MST.

Here is the efficient algorithm to find all superheavy edges in general cases. Its time-complexity is about the time-complexity to sort the edges by weights, or $$O(m\log m + n)$$, where $$n$$ is the number of vertices and $$m$$ is the number of edges. Its space-complexity is about $$O(m+n)$$.

1. Sort all edges in groups of increasing weights so that we have $$E=E_1\cup E_2\cup \cdots \cup E_r$$ and $$w_1 where $$E$$ is the edge set of $$G$$ and every edge in $$E_i$$ has weight $$w_i$$.
2. Let $$H$$ be a graph that has the same vertices as $$G$$ but without any edges. Track the connected components of $$H$$ by a disjoint-set data structure.
3. For $$i$$ from 2 to $$r$$ do the following.
1. Add all edges in $$E_{i-1}$$ to $$H$$.
2. For each edge in $$E_i$$, check whether its endpoints are in the same connected component of $$H$$. If yes, it is a superheavy edge.