Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
According to this wikipedia link, under the title "Success probability of the contraction algorithm": Number of possible cuts in a graph is $2^{n-1}-1$, while maximum number of minimum cuts is ${n}\choose{2}$, where $n$ is number of vertices.
My question:
Why number of possible cuts differ from maximum number of minimum cuts? why isn't any cut a candidate minimum cut?
In a specific graph, not any cut is a minimum cut. What Wikipedia claims is that out of the $2^{n-1}-1$ potential cuts, at most $\binom{n}{2}$ can be minimum cuts in any given graph. Some graphs contain even fewer minimum cuts. For example, if you connect two cycles by a single edge then there is a unique minimum cut.
The upper bound on the number of minimum cuts follows by analyzing Karger's algorithm (linked to in the question): you can show that the probability that the algorithm produces any specific minimum cut is at least $1/\binom{n}{2}$, and so there can be at most $\binom{n}{2}$ of them.
