Let "output" denote the cut output by Karger's min cut algorithm on a given connected graph with n vertices, and let p=1n2. 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".
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 and every min cut (A,B),
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, there exists a min cut (A,B) of G such that
Pr[out=(A,B)]≥p.
For every graph G with n nodes and every min cut (A,B) of G,
Pr[out=(A,B)]≥p.