What edges are not in any MST?
A Google search for &quot;edges not in MST&quot; 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 &quot;if&quot; part, a superheavy edge is not in any MST, is proved in the cycle property of MST.
The &quot;only if&quot; 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 &quot;only if&quot; 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 &quot;only if&quot; 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)$. 

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&lt;w_2&lt;\cdots&lt;w_r,$$ where $E$ is the edge set of $G$ and every edge in $E_i$ has weight $w_i$.
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.
For $i$ from 2 to $r$ do the following.

Add all edges in $E_{i-1}$ to $H$.
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.