2
$\begingroup$

For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.

My attempt to prove this was using a contradiction argument, supposing there was a common edge across 2 different min-cuts. Also, there is an edge in one min-cut that does not exist in the other, and idem for the other cut. Name these e1 and e2.

I managed to prove that the common edge must be an edge on a path between an end-point of e1 and one of e2.

There is a figure I drew to understand the situation better: enter image description here

$\endgroup$
1
$\begingroup$

Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?

There is no "why" here since 2 different edge minimum-cuts in an undirected multigraph can have one edge in common.

Here is an example. Edge set $\{AB,AC\}$ is a minimum cut. Edge set $\{AB,BC\}$ is another minimum cut. They have edge AB in common.

enter image description here

For the proof of a maximum of $\binom n2$ min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.

I do not think we need that (non)-fact. The random contract algorithm will find each min-cut with a probability of no less than $\frac1{\binom n2}$. Since that algorithm only find one min-cut each time, there are at most $\binom n2$ min-cuts.


Here are several exercises to enhance our understanding of the intersection of two min-cuts.

(Exercise 1). Find an undirected multigraph in which 2 different edge minimum-cuts have 2 edges in common.

(Exercise 2). Find an undirected simple graph in which 2 different edge minimum-cuts have 2 edges in common.

(Exercise 3). Given a positive integer $n$, find an undirected simple graph in which 2 different edge minimum-cuts have $n$ edges in common.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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