Decide Whether There Exists a MST That Contains a Given Edge in Linear Time

Question

Let G = (V, E) be a weighted, connected and undirected graph and let e be any edge in E. Show a linear time algorithm that decides whether there exist a Minimum Spanning Tree that contains the edge e.

I managed to find a strange "solution" to question 1 and it seems to work but I don't think it's linear:

They suggested using union find and do Union(u,v) for each edge (u,v) such that W(u,v) < W(e). Now, assume that e = (x,y). Now if find(x) != find(y) then x and y aren't connected, and W(e) would certainly be the next weight that will be examined by Kruskal's algorithm, so there surely exists a MST that contains the edge e.

On the other hand, if find(x) = find(y) then if we ran Kruskal algorithm to this point, x and y would certainly be connected, so we cannot add the edge e to any MST (and it’s known that by manipulating the sorted order of the edges that have equal weight - Kruskal’s algorithm can be used to create any MST).

I don't understand why is this linear ? Isn't it supposed to cost O( |E| alpha(|V|) ) because of the unions ?

Perhaps there is another way to do this in linear time ?

Thanks in advance

Answer 1

If we take Kruskal's algorithm to "this" point, mark connected components built so far, and add all the dropped edges back, each connected component will still contain all the same vertices as before (dropped edges only add cycles, not connect different components). So we only need to check whether e connects two different connected components made up with edges strictly lighter than e. Finding connected components is a linear time job.