What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph?
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