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.
Note: Falk's algorythm can be used to find both a minimum cut with minimum vertices and with maximum vertices. For the latter the algorythm should be reversed, ie. search from the sink vertex instead of the source. See a related question: [Network Flow: Adding a new edge](https://stackoverflow.com/questions/8019906/network-flow-adding-a-new-edge)