# Algorithm to Find All Vital Edges in a Minimum Weight Spanning Tree

I am trying to locate an algorithm that can find ALL vital edges (edges whose deletion strictly increases the cost of the minimum weight spanning tree in the resulting graph) in a minimum weight spanning tree, but have been unable to do so. There appear several algorithms for finding the most vital edges in a minimum weight spanning tree, but not all vital edges in general, and I'm not sure why this is the case.

Any help or assistance would be much appreciated.

Thank you.

-

To determine if a given edge $e$ is vital or not, I suppose you can do the following.
Find a minimum spanning tree. If the tree contains the edge $e$, change the weight of $e$ to $\infty$ and find a minimum spanning tree again. If the weight of the minimum spanning tree increases, then $e$ is vital, otherwise it is not.
This is just trying to recast your delete step. Instead of delete, we set its weight to $\infty$ effectively deleting it.