CareerCup

Let "output" denote the cut output by Karger's min cut algorithm on a given connected graph with n vertices, and let p=1/(n "up" 2). Which of the following statements are true? For hints on this question, you might want to watch the short optional video on "Counting Minimum Cuts".
For every graph G with n nodes and every min cut (A,B) of G,

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

Pr[out=(A,B)]≤p.
For every graph G with n nodes and every min cut (A,B),

Pr[out=(A,B)]≤p.
There exists a graph G with n nodes and a min cut (A,B) of G such that

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

Pr[out=(A,B)]≥p.