Given an undirected and connected graph G(V,E) with weight function w:E->R, an edge e(u,v) belongs to E. Which algorithm that runs in linear run-time complexity can assure if there's a minimal spanning tree that contains the edge e?
Perform depth-first search starting from u and ignoring any edge with weight equal to weight of given edge or heavier. If DFS completes without visiting v, this means there is no cycle where given edge is the heaviest edge, therefore given edge is contained in some minimal spanning tree.