V … number of vertices

• Probability of contract to result in a minimum cut: ≥ `1 // ``((V),(2))`
• This is much higher than the probability of picking a minimum cut at random, which is ≤ `((V),(2))` `// (2^(V-1) - 1)` because every graph has 2^V-1-1 cuts, of which at most `((V),(2))` can have minimum weight
• Single edge contraction can be implemented in O(V) time on an adjacency-list representation ⇒ total running time: O(V²)

  (Best known implementation uses O(E) time)