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.

Note: I haven't tried proving it.