## Randomized Min-Cut Algorithm

We assume that mininmal cut has a size of k. Due to this assumption, every vertex in the graph must have a degree of at least .
The number of edge-vertex pairs is at least . Every edge is incident to two vertices, that is why the number of edges in is at least .
Probability of choosing an edge in the min-cut() in the contraction is:
Pr( e min-cut(G)) =
Pr( e min-cut(G))
Pr( e min-cut(G))
Pr( e min-cut(G)) 1-
Pr( e min-cut(G))
In the last iteration :
Pr( e min-cut(G)) 1-
Pr( e min-cut(G))

During all iterations of the contraction algorithm, if we do not contract any of the edges that belong to min cut, we will successfully find the min-cut. Probability of this is:
Pr(success)
Pr(success)
Pr(success)
This result conforms to the lemma put forth by R. Motwani et al. [6].
Lemma: Suppose that the Algorithm Contract is terminated when the number of vertices remaining in the contracted graph is exactly . Then any specific min-cut survives in the resulting contracted graph with probability at least .

Subsections
Ali Salehi 2005-04-29