Question: I need to find the minimum cut on a graph. I've been reading about flow networks, but all I can find are maximum flow algorithms such as Ford-Fulkerson, push-relabel, etc. Given the max flow-min cut theorem, is it possible to use one of those algorithms to find the minimum cut on a graph using a maximum flow algorithm? How?

The best information I have found so far is that if I find "saturated" edges i.e. edges where flow equals capacity, those edges correspond to the minimum cut. Is that true? It doesn't sound 100% right to me. It is true that all edges on the minimum cut will be saturated, but I believe there might also be saturated edges which are out of the minimum cut "path".

Answer: 
I don't want to be picky, but the suggested solution is not quite right as proposed.

**Correct solution**: What you actually should be doing is bfs/dfs on the *Residual-Network Gf* ([read it up on wikipedia](http://en.wikipedia.org/wiki/Flow_network)) and marking vertices. And then you can pick those with marked from-vertex and unmarked to-vertex.

**Why 'following unsaturated edges' is not enough**: 
Consider, that the flow algorithm saturates the edges as shown in the picture. I marked the vertices I'm visiting with the approach of "just following unsaturated edges" with green. Clearly the only correct min-cut is the edge from E-F, while the suggested solution would also return A-D (and maybe even D-E).

[![enter image description here](https://i.stack.imgur.com/e4vnX.jpg)](https://i.stack.imgur.com/e4vnX.jpg)
Note that the vertex D would be visited by the dfs/bfs if we considered the Residual network instead, because there'd be an edge from E to D, thereby making the edge E-F the only one with a marked from-vertex and an unmarked to-vertex.
I think this is what other people are saying, but I found it unclear so here's my explanation:

From the source node, do a flood fill of the graph, travelling only along edges with residual capacity, marking each visited vertex. You can use a DFS for this. Recall that back edges from a vertex have a residual capacity - equal to the flow along the forward edge (ie. r(u, v) = remaining capacity for edge (u, v), r(v, u) = flow(u, v)).

In effect, this determines the S part of the S-T cut of the graph.

The minimum cut will now be the set of edges such that one vertex is marked from your flood fill above, and the other vertex is not marked. These will be edges without residual capacity (otherwise you would have traversed them in your DFS), and together form the minimum cut.

After removing these edges, the set of unmarked vertices will form the T section of the cut.