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.