How many pairs of edges can disconnect a biconnected graph?

The statement is true. In fact, much more general statements are true. If $G$ is a graph with $n$ vertices and $c$ is the cardinality of a minimum edge cut of $G$, then the number of edge cuts of cardinality $c$ is at most $binom{n}{2}$, and for every half-integer $k geq 1$, the number of edge cuts containing at most $kc$ edges is bounded above by $2^{2k-1} binom{n}{2k}.$

The upper bound of $binom{n}{2}$ on the number of minimum cuts is attributed to Bixby and Dinitz-Karzanov-Lomonosov. The more general bound on the number of approximate minimum cuts is due to Karger (Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm), who also re-proved the $binom{n}{2}$ bound on minimum cuts. His appealingly simple proof rests on the analysis of a simple "randomized contraction" algorithm. Here we present the proof that the number of minimum cuts is at most $binom{n}{2}$.

Suppose that $G$ is a multigraph with $n$ vertices, $c>0$ is the number of edges in a minimum cut of $G$, and $A$ is a specific set of $c$ edges whose removal disconnects $G$. Repeatedly perform the following process to obtain a sequence of multigraphs $G = G_0, G_1, ldots, G_{n-2}$: choose a uniformly random edge of $G_t$ and contract it to obtain $G_{t+1}$. In other words, if $(u,v)$ is the edge chosen in step $t$, then we replace $u$ and $v$ with a single vertex $z$ in $G_{t+1}$, and we replace every edge of $G_t$ having exactly one endpoint in ${u,v}$ with a corresponding edge of $G_{t+1}$ with endpoint $z$. (Edges from $u$ to $v$ in $G_t$ are deleted during this step.) Note that $G_{n-2}$ has exactly two vertices $a,b$, these vertices correspond to a partition of $V(G)$ into two nonempty sets $A,B$ (those vertices that were merged together to form $a in V(G_2)$, and those that were merged together to form $b$), and that the edges of $G_{n-2}$ are in one-to-one correspondence with the edges of the cut separating $A$ from $B$ in $G$. Denote this random cut by $R$.

Now consider a specific cut $C$ of cardinality $c$. We claim that the probability of the event $R=C$ is at least $1 left/ binom{n}{2} right.$, from which it follows immediately that the number of distinct cuts of cardinality $c$ is at most $binom{n}{2}$. To prove the upper bound on the probability that $R=C$, observe that for all $t = 0,ldots,n-2$, every vertex of $G_t$ has degree at least $c$. (Otherwise, that vertex of $G_t$ corresponds to a set of vertices in $G$ having fewer than $c$ edges leaving it, contradicting our assumption about the edge connectivity of $G$.) Consequently, the number of edges of $G_t$ is at least $(n-t)c/2$, and the probability that an edge of $C$ is contracted in step $t$, given that no edge of $C$ was previously contracted, is at most $c/|E(G_t)| leq 2/(n-t)$. Combining these bounds, we find that the probability that no edge of $C$ is ever contracted is bounded below by $prod_{t=0}^{n-3} left(1 - frac{2}{n-t}right) = frac{n-2}{n} cdot frac{n-3}{n-1} cdots frac{1}{3} = frac{2}{n(n-1)}.$

• Next Some arithmetic terminology: "universal domain", "specialization", "Chow point"
• Previous rt.representation theory - reference on examples of (g, K)-modules