# How to find the subsets S and T and the min-cut of this graph?

I get the residual graph by Ford-Fulkerson Algorithm:

I get that the minimum cut can be found by 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 $$S$$, the rest of the nodes are called $$T$$. 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 $$S$$ to a node in $$T$$.

So I think $$S = \{S, C, E\}$$, and $$T = \{T, A, B, D, F\}$$. But I found that what I found was not the minimum cut and two subsets I wanted. Why? Is my residual graph wrong?

• Can you please show a flow that would produce that residual graph?
– JimN
Commented May 2, 2023 at 9:04
• Of course, I've put it on Commented May 6, 2023 at 9:58
• Yes, your residual graph is wrong. The residual graph should include all your blue arcs in your diagram. For example, since there is a flow of 4 from A to E, the residual graph should include an arc from E to A of capacity 4 (representing the possibility of "pushing back" 4 units of flow there). So your partition of {S,C,E} should be including more nodes, like A as I just described.
– JimN
Commented May 6, 2023 at 10:04
• Thank you! I understand that I should only delete the flow with a weight of 0, not the reverse flow, right? Commented May 6, 2023 at 12:03
• Correct, the non-zero reverse flow arcs are a part of the residual graph
– JimN
Commented May 6, 2023 at 17:27

The residual graph, as presented, is incomplete. The residual graph must include the non-zero reverse flow arcs. Then anything reachable from the source $$S$$ in that residual graph forms one part of the partition of the min cut.