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:
- When the number of edges is too small, the graph is almost never connected. (So if $k$ is large, almost all $\binom mk$ sets of $k$ edges are cuts.)
- When the number of edges is large enough, the graph is almost always connected. (We're not interested in this case.)
- Around the boundary, whether the graph is connected or disconnected depends almost solely on whether there are isolated vertices.
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:
- When I took $1000$ random graphs with $200$ vertices and $1000$ edges, $995$ were connected and $5$ had an isolated vertex.
- When I took $1000$ random graphs with $200$ vertices and $600$ edges, $635$ were connected, $363$ had one or more isolated vertices, and only $2$ had a component of order $2$.
- When I took $1000$ random graphs with $2000$ vertices and $10000$ edges, $910$ were connected and $90$ had one or two isolated vertices.
- When I took $1000$ random graphs with $2000$ vertices and $6000$ edges, only $3$ were connected, but only $34$ were disconnected for reasons other than having isolated vertices.
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.
