The unique heaviest edge on a graph cycle belongs to no minimum spanning tree. If a spanning tree contains it, deleting it gives two components; the rest of the graph cycle has a lighter edge across that cut of a graph. Insert that edge to reduce the weight. This is the deletion certificate used by the reverse-delete algorithm.
Articles by others on the same topic
There are currently no matching articles.