# Network Flow: Algorithm to find a cut of smallest capacity among all cuts

You are given a flow network $$G$$ with $$n > 4$$ vertices. Besides the source $$s$$ and the sink $$t$$, you are also given two other special vertices $$u$$ and $$v$$ belonging to $$G$$. Describe an algorithm which finds a cut of the smallest possible capacity among all cuts in which vertex $$u$$ is at the same side of the cut as the source $$s$$ and vertex $$v$$ is at the same side as sink $$t$$.

• Welcome to Stackexchange. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance – Brian Apr 9 at 10:10
• Let me know when you find a solution! – mathpadawan Apr 10 at 2:24

Let's contract $$s$$ and $$u$$ into $$s'$$, $$t$$ and $$v$$ into $$t'$$ and let the resulting graph be $$G'$$.The problem you described is equivalent to the problem of finding a minimal $$s'-t'$$ cut in $$G'$$, which I'm sure you know how to solve.
I'm sorry but I have to tell I don't know how to contract $$s$$ and $$u$$.Could you tell more details?