The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph.
Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it.
This bound is achieved as follows: It is recommended to read the proof of the Kruskal's algorithm first.
First, it is proved that the edges that remain after the algorithm is applied form a spanning tree.
Thus g must be a spanning tree of the main graph G. We show that the following proposition P is true by induction: If F is the set of edges remained at the end of the while loop, then there is some minimum spanning tree that (its edges) are a subset of F.