 Reverse-delete algorithm

The reverse-delete algorithm processes edges of a finite connected undirected weighted graph in nonincreasing weight order, deleting an edge whenever the graph stays connected.

Maintain the invariant that the surviving graph contains some minimum spanning tree. A deletable edge $e$ lies on a cycle. Previously retained heavier edges are bridges and remain bridges after further deletions, so every other edge on that cycle has weight at most $w(e)$. If a current optimum contains $e$, removing it creates a cut. Another cycle edge $f$ crosses that cut; replacing $e$ by $f$ gives a surviving tree of no greater weight. Thus an optimum remains after deleting $e$.

At termination the graph is connected and acyclic, hence is itself a minimum spanning tree. With tied weights, $e$ need not be excluded from every optimum. On a triangle with all weights one, every edge belongs to some optimum, yet deleting any one edge is safe. The minimum spanning tree cycle property excludes an edge from every optimum only when it is uniquely heaviest on a cycle.

The Reverse-Delete algorithm is a graph algorithm used to find the minimum spanning tree (MST) of a connected and undirected graph. It is based on the concept of deleting edges and checking connectivity, which is a complement to the more commonly known Prim's and Kruskal's algorithms for finding MSTs. ### How the Reverse-Delete Algorithm Works: 1. **Initialization**: Start with the original graph, consisting of vertices and edges.