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

My motivation is to find what edges of an weighted, undirected graph are not a part of any 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 - instead of adding the minimum edge from S to T on every step (where S and T being the two sets of vertex) - instead 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 receive 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.

in an unweighted, undirected graph, minimum spanning tree doesn't have meaning. Any spanning tree will do, that is, any acyclic connected subgraph, $(V, E' \subseteq E)$, where the original graph has vertices and edges: $(V,E)$. –  Joe Dec 10 '12 at 23:13
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