I know how Karger's algorithm works, and that the probability of finding a min-cut is over $1/n^2$. My question is the following. How can I find the probability of not contracting edges of a min-cut on a graph by running this algorithm?
Suppose I have the two graphs below:
The probability of finding a min-cut on the left graph is 1/2, as the probability of not contracting the edge c-d in the 1st run is 3/4 and then (no matter which edge out of a-b,b-c,a-c I have contracted, the resulting graph is the same) and the probability of not contracting c-d is now 2/3 giving as a result 1/2.
On the next graph, though, things are different. Let's say I want to find the probability of not contracting the edge c-d. If 2 first contractions are on any of the three edges on the left, then the possibility of not contracting c-d is 1/2, On the other hand, if the first contraction is on d-e and the 2nd on a-b then the probability of not contracting c-d is now 2/3. How do I find the total probability in these cases?
