<p>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.</p>

CC BY-SA 2.5
2010-08-27T07:26:58.920Z
@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
CC BY-SA 2.5
2010-08-27T07:30:58.033Z
...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
CC BY-SA 2.5
2010-08-17T05:14:43.787Z
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
CC BY-SA 2.5
2010-08-16T22:43:40.043Z
2010-08-16T22:43:40.043Z
ilyaraz
<p>This is not a well-defined algorithm. You can tweak it to make it well-defined, by changing the description to</p>

<pre><code>Remove all edges, from high to low weight, that do not make the graph disconnected.
</code></pre>

<p>and this is equivalent to kruskal's algorithm.</p>

CC BY-SA 2.5
2010-08-17T05:10:29.050Z
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
CC BY-SA 2.5
2010-08-16T22:44:43.583Z
2010-08-16T22:44:43.583Z
Alexandre Passos
<p>Is the following a valid algorithm for finding a minimum spanning tree?</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-08-16T22:44:17.907Z
maybe this is a good example of something off topic as being too easy to find on wikipedia ?
Suresh Venkat
CC BY-SA 2.5
2010-08-16T22:44:48.437Z
I agree to Suresh.
ilyaraz
CC BY-SA 2.5
2010-08-17T05:17:36.730Z
@ilyaraz: I've looked into this some before and never seen the characterization you referenced in your answer.
BCS
<ds.algorithms><graph-algorithms>
Minimum spanning tree algorithm.
BCS
# Minimum spanning tree algorithm.

(Asked by: username_0 on 2010-08-16)

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.

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: maybe this is a good example of something off topic as being too easy to find on wikipedia ?  
> **username_2**: I agree to Suresh.  
> **username_0**: @ilyaraz: I've looked into this some before and never seen the characterization you referenced in your answer.  

---

## 2 answers

### Answer by username_2 on 2010-08-16. Score: 2

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: @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...  
> **username_3**: ...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.)  

---

### Answer by username_4 on 2010-08-16. Score: 2

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.

> **Comments:**
> **username_0**: 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.  

---

