Min cut of at most k edges

Question

I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle.

Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow \mathbb{N}$, find an efficient algorithm to determine whether the graph has a min cut of at most $k$ edges (assume $k=100$).

My thinking was computing a min cut, then for every edge on that cut, increase it by 1 and compute the min cut again - if the max flow has risen, that means that that edge exists in every single min cut. And If I found there to be over 100 of these edges, then there is no min cut of at most $k$ edges.

However, I don't think that if I found there to be less 100 of these edges, there's necessarily a min cut of at most 100 edges.

Answer 1

Apply the transformation $w \mapsto (m+1)w + 1$ to all weights (where $m$ is the number of edges in the graph), and find the minimum weight cut in the new graph. This will give you the minimum weight cut with the minimum number of edges. By computing the value modulo $m+1$, you can determine the number of edges.