Minimal cuts in network.

Question

Let $(S_1, \overline{S_1} ) , (S_2, \overline{S_2} )$ be minimum cuts in some network.

Thesis: The $(S_1 \cap S_2, \overline{S_1 \cap S_2)}$ is minimum cuts in this network.

Thesis is true? Why? I am asking for an advice. Thanks in advance! :)

Answer 1

It's true. It follows from the submodularity of the (directed or not) graph cut function with non-negative weights.

To prove it, I think the only useful advice it to work in cases: given a graph with edge weight function $\delta$ and two sets $S$ and $T$ of vertices, separate the cases of the edges going from $S \setminus T$ to $T \setminus S$; from $S \setminus T$ to $\overline{S \cup T}$; from $T \setminus S$ to $S \setminus T$; from $T\setminus S$ to $\overline{S \cup T}$, from $S \cap T$ to $S \setminus T$, from $S \cap T$ to $T \setminus S$ and from $S \cap T$ to $\overline{S \cup T}$. Then identify which terms contribute to $\delta(S)$, $\delta(T)$ and $\delta(S \cap T)$.