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.
(See also here for a related question.)
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.
