Give each edge weight and use Kruskal's algorithm to find a minimum spanning tree . The minimum cost is
Output an order that removes all edges outside this tree first, then the tree edges. The order within each part is arbitrary.
The time complexity is and the space complexity is .
Proof
Exactly removals increase the number of connected components. If we reverse the process, these edges join different components and connect all vertices. Thus, they form a spanning tree.
Charge every edge a base cost of . An edge in this tree costs instead, adding . The base cost is fixed, so a minimum spanning tree minimizes the additional cost and gives a lower bound.
During the first part of the proposed removal order, the surviving tree keeps the graph connected. During the second part, the remaining graph is a forest, so every removal disconnects its endpoints. This order attains the lower bound.
