Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 2

Problem:

Let "output" denote the cut output by Karger's min cut algorithm on a given connected graph with $n$ vertices, and let $p=\frac{1}{\left(\begin{array}{c}n \\ 2\end{array}\right)}$. Which of the following statements are true?

[Choices elided]

Solution:

We know that the probability of finding any fixed minimum cut is lower bounded $p$, so these two options is automatically true.

For every graph G with n nodes, there exists a min cut (A,B) such that
$Pr[out=(A,B)] \ge  p$

For every graph G with n nodes and every min cut (A,B) of G,
$Pr[out=(A,B)] \ge  p$

What is non-trivial is that whether or not there exists a graph and a min-cut such that the probability of finding it is at most $p$. This is possible, for example, a graph with only two nodes and one edge, the probability of finding the min cut is 1 and that is also the same value for $p$. Therefore this is also a correct option.

There exists a graph G with n nodes and a min cut (A,B) of G,
$Pr[out=(A,B)] \le  p$

This is a tricky question and I screwed this one the first time.