Confusion About Min-Cut Probabilities

Question

• Currently going through a video on Counting Minimum Cuts by Tim Roughgarden.
• $(A_{i},B_{i}) = \big((A_{1},B_{1}), ..., (A_{t},B_{t})\big) \forall i \in \Bbb{R}$
• $P\big((A_{i},B_{i})\big) \geq \frac{1}{\begin{pmatrix} n \\ 2 \end{pmatrix}} = p$, which I interpret as the lower bound on the probability of having at least one minimal cut.
• In the problem set that follows two answers A and B are highlighted as being correct. I understand why A is correct; but am puzzled why B is also marked as correct.
• A: For every graph $G$ with $n$ nodes and every min cut $(A,B)$ (I am assuming same thing as $(A_{i},B_{i})$) $P\big((A,B)\big) \geq p$.
• B There exists a graph $G$ with $n$ nodes and a min cut $(A,B)$ (again assuming same thing as $(A_{i},B_{i})$) of $G$ such that $P\big((A,B)\big) \leq p$.

Answer 1

I don't understand what you mean by "$(A_i,B_i) = ((A_1,B_1),\ldots,(A_t,B_t))$", an obviously false statement. Perhaps you meant $(A_i,B_i) \in \{(A_1,B_1),\ldots,(A_t,B_t)\}$?

I don't quite understand your interpretation of the statement $P((A_i,B_i)) \geq p := 1/\binom{n}{2}$. Here is the correct interpretation:

For any minimum cut $C$, the probability that Karger's algorithm outputs $C$ is at least $p := 1/\binom{n}{2}$.

This is exactly what A states.

For B, you need to give an example of a graph which satisfies $P(C) \leq 1/\binom{n}{2}$ for all cuts $C$. One such example is a cycle, an example you were probably shown in class.