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

Question

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:

Answer 1

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.