title: Find whether a minimum spanning tree contains an edge in linear time?
body: <p>I have the following problem on my homework:</p>
  
  <blockquote>
    <p>Give an O(n+m) algorithm to find that whether an edge e would be a part of the MST of a graph</p>
  </blockquote>
  
  <p>(We are allowed to get help from others on this assignment, so this isn't cheating.)</p>
  
  <p>I think that I could do a BFS and find if this edge is a edge between two layers and if so whether this edge was the smallest across those layers.  But what could I say when this edge is not a tree edge of the BFS tree?</p>