# Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found.

However, if you then use the left-over residual graph to produce a min-cut (by flood-filling outward from s along any edges or reverse edges with left-over capacity), it seems the same cut is obtained regardless of which flow-graph you use.

Is this true?

Is there a way to iterate over all cuts such that each iterator-step requires only polynomial time?

Yes, Ford-Fulkerson always finds the cut that is "closest" to the source. See this question for a formalization of what is meant by "closest".

A graph can contain exponentially many min-cuts, so beware that any procedure to enumerate all min-cuts must take exponential time in total in the worst case.

Based on what I've read, there are output-sensitive algorithms to enumerate all min $(s,t)$-cuts. After a single maximum flow computation, the running time is $O(n)$ per min-cut that is output. Details can be found in the following paper:

Jean-Claude Picard, Maurice Queyranne. On the structure of all minimum cuts in a network and applications. Combinatorial Optimization II: Mathematical Programming Studies, volume 13, 1980, pp.8--16.
Unfortunately, there does not seem to be a non-paywalled online version of the paper.

In contrast, if you want to find all min-cuts of an undirected graph, rather than all min $(s,t)$-cuts, you can use Karger's algorithm to do that efficiently (in polynomial time).
Just adding to the answer of D.W.. Following is a simple example of a graph network that contains an exponential number of $$(s,t)$$ min cuts.
Let the vertex set be $$V = \{s\} \cup \{u_{1},\dotsc,u_{n}\} \cup \{v_1,\dotsc,v_n\} \cup \{t\}$$. Let the edges set contains the directed edges $$(s,u_{i})$$, $$(u_{i},v_{i})$$, and $$(v_{i},t)$$ for each $$i \in \{1,\dotsc,n\}$$. Therefore, there are total $$3 n$$ edges. Each edge has capacity $$1$$.
The max-flow on this network is $$n$$.
The min-cut cut obtained using Ford-Fulkerson algorithm is $$\left(\{s\}, V \setminus \{s\}\right)$$.
There are other $$(s,t)$$ min cuts in the graph as follows. Let $$C = (S,T)$$ be a cut such that $$S$$ contains the vertex $$s$$ and all the vertices in the set $$\{u_1,\dotsc,u_n\}$$. It is optional to include a vertex $$v_{i}$$ in the set $$S$$. The remaining vertices, i.e., $$V \setminus S$$ belongs to $$T$$. Any such cut has a capacity $$n$$. Therefore, it is a min-cut. Since there are $$2^n$$ choices of including $$v_{i}'s$$, the total number of min-cuts are $$2^n \in 2^{O|V|}$$. Hence, we get an exponential number of min-cuts.