 The "cutset" of a cut consists of the edges formula_11 between the two parts.The "size" (or "weight") of a cut in an unweighted graph is the cardinality of the cutset, i.e., the number of edges between the two parts, 
There are formula_13 ways of choosing for each vertex whether it belongs to formula_14 or to formula_15, but two of these choices make formula_14 or formula_15 empty and do not give rise to cuts.Among the remaining choices, swapping the roles of formula_14 and formula_15 does not change the cut, so each cut is counted twice; therefore, there are formula_20
The probability formula_21 that the contraction algorithm on an formula_22-vertex graph avoids formula_23 satisfies the recurrence formula_24, with formula_25, which can be expanded as

By repeating the contraction algorithm formula_27 times with independent random choices and returning the smallest cut, the probability of not finding a minimum cut is

The total running time for formula_15 repetitions for a graph with formula_22 vertices and formula_31 edges is formula_32.