# Minimum spanning tree algorithm. [closed]

Is the following a valid algorithm for finding a minimum spanning tree?

Given a weighted graph with unique weights, remove the all edges that are the highest cost edge in any cycle of the original full graph.

Edit: I've changed the description to draw more attention to the differences between this an Kruskal's algorithm (which it is NOT.) Kruskal's algorithm is iterative, this is just a predicate that can be tested on the original unmodified graph.

• maybe this is a good example of something off topic as being too easy to find on wikipedia ? – Suresh Venkat Aug 16 '10 at 22:44
• I agree to Suresh. – ilyaraz Aug 16 '10 at 22:44
• @ilyaraz: I've looked into this some before and never seen the characterization you referenced in your answer. – BCS Aug 17 '10 at 5:17

Indeed, it is correct. You can characterize MST as a tree such that every edge outside it is a maximum edge in the corresponding cycle. The proof is an easy excersise.

• Do you have a reference to such a characterization? -- I think you are correct, but I'm not 100% sure that that shows that the edges in the MSP can't be a minimum edge in any cycle. – BCS Aug 17 '10 at 5:14
• @BCS: I think you mean you're not sure that that shows that the edges in the MST can't be a maximum edge in any cycle, right? Consider any cycle in the original graph, with maximum edge length between u and v, and suppose that there is an MST containing uv. Deleting that edge gives a graph with a u-containing component and a v-containing component. Now convince yourself that there must be at least 2 edges on the original cycle that span these 2 components: we already know there must be at least 1 (the edge we just deleted), and if you trace around the cycle you must... – user651 Aug 27 '10 at 7:26
• ...come back to the component you started from at least once. So, there are at least 2 spanning edges, and adding either one will reconnect the graph. Adding back any of the non-uv (= non-max-length) edges will produce a connected graph with shorter length than we started with, hence the original graph could not have been a MST. (Proof by contradiction.) – user651 Aug 27 '10 at 7:30

This is not a well-defined algorithm. You can tweak it to make it well-defined, by changing the description to

Remove all edges, from high to low weight, that do not make the graph disconnected.


and this is equivalent to kruskal's algorithm.

• This algo is not iterative. Kruskal's is. This algo only looks at the origonal graph. Kruskal's looks at the graph after edges have been removed. This algo is not Kruskal's. – BCS Aug 17 '10 at 5:10