title: Decide Whether There Exists a MST That Contains a Given Edge in Linear Time
body: <p>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.</p>
  
  <p>I managed to find a strange "solution" to question 1 and it seems to work but I don't think it's linear:</p>
  
  <p>They suggested using union find and do Union(u,v) for each edge (u,v) such that W(u,v) &lt; 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.</p>
  
  <p>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).</p>
  
  <p>I don't understand why is this linear ? Isn't it supposed to cost O( |E| alpha(|V|) ) because of the unions ?</p>
  
  <p>Perhaps there is another way to do this in linear time ?</p>
  
  <p>Thanks in advance</p>