I have the following problem on my homework:

Give an O(n+m) algorithm to find that whether an edge e would be a part of the MST of a graph

(We are allowed to get help from others on this assignment, so this isn't cheating.)

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?

algorithm minimum-spanning-tree
Edit
Report