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
.