Modify the algorithm CONTRACTION in the following way. Instead of choosing an edge at random, choose two vertices x and y randomly and join them into one vertex. Construct multi-graphs of n vertices, for which the probability that the modified algorithm finds a minimal cut is exponentially small in n.