algorithm - 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

提示：对于每个边 e，存在一个包含 e 的最小权重生成森林当且仅当 e 的端点之间不存在由（严格）比 e 轻的边组成的路径。