I'm stuck with one of my homework exercises:
Consider the following variant of Karger’s algorithm for finding a minimum s-t cut, i.e., a minimum cut separating two specific given nodes s and t:
As in the original algorithm, edges are iteratively contracted. In any iteration, let s and t denote the possibly contracted nodes that contain the original nodes s and t, respectively. To ensure that s and t do not get contracted, at each iteration any edges connecting s and t are deleted, and a random edge to contract is selected from the remaining edges.
Give an example showing that the probability that this method finds a minimum s-t cut can be exponentially small.
I know how Karger's algorithm works, but I'm not sure why the probability is exponentially small and how can I show that by giving an example.
Any hint would be helpful.