Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider some biconnected graph $G$. Removing any single edge will not disconnect $G$. However, unless $G$ is triconnected, there is some pair of edges whose removal will disconnect $G$. For a cycle of length $l$, the removal of any pair will disconnect the graph (if the edges are adjacent, there will be an isolated vertex).

Conjecture: any biconnected graph on $l$ vertices has at most $\binom{l}{2}$ pairs of edges that disconnect it. Furthermore, the bound is tight only for cycles.

Is the conjecture true? I have a candidate proof but I suspect that there's a simpler one.

share|improve this question
add comment

1 Answer

up vote 11 down vote accepted

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)}.$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.