Minimum spanning tree containing a given edge after removing edges

Question

This is a part of an exam preparation. I know it has something to do with max-flow algorithm, but I'd be happy for a hint:

Let G=(V,E) an undirected connected graph, and let w:E->R a weight function, e an edge and k > 0. Describe an algorithm that determines whether we can remove at most k edges from the graph, so that e would belong to a minimum spanning tree of the new graph.

I think that a spanning tree is kind of a perfect matching. But how do I make it minimal that contains e and the right amount of other edges?

Answer 1

Hint: for every edge e, there exists a minimum-weight spanning forest containing e if and only if there exists no path between e's endpoints comprised of edges (strictly) lighter than e.