What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph? I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of

Counting the number of distinct s-t cuts in a oriented graph

It says that due to this consequnce, the cuts of an unweighted graph can be listed in polynomial time, but the claim is unreferenced.
If you want exact minimum cuts then one can construct a cactus representation of the minimum cuts deterministically in polynomial time and use that to enumerate all minimum cuts. See below for a reference. https://www.sciencedirect.com/science/article/pii/S0196677499910398

More interesting and difficult case is $\alpha$-approximation mincuts for $\alpha &gt; 1$. One can use Karger's randomized algorithm for this purpose. Simply run it sufficiently many time. However, if you want a deterministic algorithm, one can do it via tree packings. See Thorup's paper on k-cuts. https://dl.acm.org/citation.cfm?id=365415