The question asks about an undirected graph. The solution is to check for K disjoint paths. But, both MST and Flow algorithms work on directed graphs. In order to make the graph directed we need to change each edge to be two edges in the opposite directions. In this case the K paths we find might belong to K/2 paths in the original graph (if we select all double edges of the original edges) and the algorithm might say that we cannot remove atmost K paths to make e be a part of a MST, while if we remove up to K undirected edges we might get a MST with e as one of its' edges.

How is it possible to solve this issue?

Thanks!

HW5 q7