V … number of vertices

• Fact. 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 and
  • Fact. At most `((V),(2))` cuts 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 of graph contraction uses O(E) time)