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.