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

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: 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. 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.