reverse greedy algorithm I got this reverse greedy algorithm here as below:
First we sort edges of G in decreasing order, as e_1 > e_2　> ... e_m
Then begin with T := G
for i=1,2,...,m 
if T-e_i is connected, then T:= T-e_i
end
How do we show the output is a minimum spanning tree? 
I want to show it is a spanning tree first, which I know V(T)=V(G), and also if there is any cycle, the edges on cycle will be deleted as after deleting one edge cycle is still connected and therefore we will update graph. So output contains no cycle.
But how do we show it has minimum total weight as well? I can see it is very clear the case, but don't know what is a good way to set up the proof. Can anybody please give me a hand? Thanks a lot.
 A: Let the minimum spanning tree $M$ have edges $f_1 > f_2 > \cdots > f_m$. If it is not the same one as the one produced by the above algorithm (let's call it $A$), then there is $k$ such that $e_k \in A \setminus M$, $f_k \in M \setminus A$, and $e_i \in A \cap M$ for all $i < k$. In plain words, $k$ is the index of the first edge that doesn't belong in the minimal tree, but your algorithm would pick it anyway.
Now, take a look at the algorithm. What can you say for $e_k \lesseqqgtr f_k$?
Let me give you an additional hint, for this part only. Your algorithm takes edges by their weight, as long as they don't close cycles. This means that $f_k \not\in \{e_1,\dots,e_k\}$. To see that this is true, just assume the opposite, i.e., $f_k = e_i$ for some $i < k$. Obviously, $f_k = e_i \not\in A$, and you get a contradiction ($f_k = e_i$ closes a cycle; otherwise, your algorithm would pick it). What do you conclude from that, regarding $e_k \lesseqqgtr f_k$?
Do this for all such $k$ and you should have your proof.
