# How to find a minimum cut of a network flow?

I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph.

Could someone explain how to find the minimum cut of this graph? I THINK the minimum capacity is 4.

• For an example of this size, enumerate all cuts. – Raphael Dec 4 '14 at 14:23
• Are you sure you meant "minimum" capacity or "maximum" capacity? – SOFe Mar 22 '19 at 5:01

Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition $A$. The rest of the nodes (the unreachable ones) can be called $B$. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in $A$ to a node in $B$.
For this specific graph, yes, the minimum cut does have capacity $4$: if you only delete one edge, there's still a path from $s$ to $t$, so you need to delete at least two edges. Deleting the edges $sB$ and $At$ disconnects $s$ from $t$ and those edges have total capacity $4$; any other pair of edges has higher capacity, so $4$ is the minimum.
minimum cut gives the maximum capacity, not the minimum capacity in above network, on deleting sB and At, you get the max-flow as 4 the min-flow can be 0 in any network without circulation, for which you dont need to determine the min-cut.
To find min-cut, you remove edges with minimum weight such that there is no flow possible from s to t. The sum of weights of these removed edges would give you the max-flow