I need to prove the statement $\exists$ a minimum cut $(S', T')$ where $S' \subseteq S$ for any minimum cut $(S, T)$

My attempt: Before proving this statement, I have a lemma if $(S_1, T_1)$ and $(S_2, T_2)$ are both minimum cuts, then $(S_1 \cap S_2, T_1 \cup T_2)$ and $(S_1 \cup S_2, T_1 \cap T_2)$ are minimum cuts as well.

My proof: let $(S_1, T_1)$ and $(S_2, T_2)$ be two minimum cuts. Based on the lemma, we have $(S_1 \cap S_2, T_1 \cup T_2)$ is a minimum cut. Also, $S_1 \cap S_2 \subseteq S$. Thus, the statement is correct. Is my proof correct?

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Oct 13 '20 at 6:25
  • 2
    $\begingroup$ Can't you just choose $(S',T') = (S,T)$? $\endgroup$ – Yuval Filmus Oct 13 '20 at 6:57

Your Answer

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

Browse other questions tagged or ask your own question.