Question

Prove the following MST algorithm is correct. You can use the cut property in your proof if you want, but it's not clear it's the best approach

sort the edges according to their weights
for each edge e ∈ E, in decreasing order of weight :
    if e is part of a cycle of G:
        G = G − e (that is, remove e from G)
return G

Answer 1

There are 2 parts in the proof:

1. No deleted edge belongs to any MST

2. The resulting tree is Spanning tree of G.

An edge is deleted in the algorithm if it part of a cycle and deleting it does not disconnects the graph:

to prove 1, proof by contradiction

Suppose that an edge e removed by algorithm is part of some MST, let M be that MST,

Since e lies on a cycle and has the largest weight, there exists some e' such that weight of e' is less than e and e' lies on the same cycle.

remove e and add e' to M, then the resulting tree has lesser weight than it started with,but we started with a MST, so it is not possible, a contradiction.

So no MST contains the edges removed by the Algorithm.

to prove 2.

proving 2 is easy, since G initially was connected , and an edge is removed iff G does not disconnects, the resulting tree is also connected, hence spanning.

so from 1 and 2 its is evident that the resulting tree by algo is MST.