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.