What is known about the distribution of edge cuts in random graphs? E.g., in the following graph:
removing edge $a$ disconnects the graph; there is only one way to cut with one edge (producing two components). Removing any of the pairs: $(a,b)$, $(a,c)$, $(a,d)$, $(b,c)$, $(c,d)$, $(b,d)$, also disconnects the graph (producing two components). So there are six ways to cut with two edges. Removing any three edges (there are four ways to do so) disconnects the graph (now producing three components). Finally, removing all four edges can be done in one way (producing four components). In this case, the distribution of cuts is:
Actually, I'm interested in the distribution of edge cuts that produce exactly two components. But if that's too difficult, any number will also work for me. I'm interested in random graph with $200-2000$ vertices.
Best Answer
Let's consider the random graph $\mathcal G_{n,m}$ with $n$ vertices and $m$ edges, and try to count the number of $k$-edge cuts.
If we pick a random $k$-edge set and delete it, what we're left with is the random graph $\mathcal G_{n,m-k}$, it's just chosen funny. We could compute the probability that $\mathcal G_{n,m-k}$ is connected, and that would tell us the fraction of the $\binom mk$ $k$-edge sets that are cuts. But I'm going to get there indirectly.
When we're trying to figure out when the random graph is connected, there are three regimes:
This is a result usually proved in the limit as the number of vertices tends to $\infty$. But it's specifically true in your range of graphs with $n \in [200, 2000]$ vertices, if we start with about $5n$ edges and delete some. For example, experimentally:
Anyway, this tells us that if we want to estimate the number of $k$-edge cuts in a random graph, we should count the number of $k$-edge sets that isolate a vertex. As a rough approximation, this is going to be $$ \sum_{i=1}^n \binom{m-d_i}{k-d_i} $$ where $d_1, d_2, \dots, d_n$ is the degree sequence of the graph. (But if you're using this as a base of comparison of your graphs with random graphs, you should also check if your degree sequence matches the degree sequence of a random graph with the same number of edges.)
The sum above is incorrect because it ignores overlap, but for small $k$, the overlap should be negligible, and for large $k$, almost all $k$-edge sets will be cuts.
In the middle range, the Poisson approximation is often used. (And actually, we can use it for any $k$.) To find the probability that a vertex in $\mathcal G_{n,m-k}$ is isolated, first approximate choosing $m-k$ edges exactly by choosing each edge independently with probability $p = (m-k)/\binom n2$. The probability that a vertex is isolated is $(1-p)^{n-1} \approx e^{-np}$, or $\exp(-\frac{2(m-k)}{n})$. So the expected number of isolated vertices is $n e^{-np}$. Call this quantity $\mu$. Then the Poisson approximation says that the probability of having no isolated vertices is about $e^{-\mu}$, which predicts that there are $(1 - e^{-\mu}) \binom mk$ $k$-edge cuts.