Showing that Karger's contraction algorithm has exponentially small probability of finding an optimum
Consider a graph $G$ with nodes $s$ and $t$, and $n-2$ other nodes $v_1, ..., v_{n-2}$. There are two parallel edges from $s$ to $v_i$, and one edge from $v_i$ to $t$. The minimum $s-t$ cut is to separate $t$ by itself. 

If we run the version of the contraction algorithm described in the problem, it will independently contract each of the length-2 paths from $s$ to $t$ in some order. In order for it to find the minimum $s-t$ cut, it must contract $v_i$ into $s$, not into $t$. There is a $\frac{2}{3}$ chance of this happening for each $i$, so the probability that the minimum $s-t$ cut is found is $(\frac{2}{3})^{n-2}$, an exponentially small quantity.

Though, I don't know whether this one works.