Note: please make sure that the proposed solution accurately asserts its claims and offers a thorough demonstration. It is rooted in the max flow min-cut theorem and does not require any additional reasoning regarding flows.

4. Let G=(V,E) be a flow network and let C denote the set of all minimum-capacity cuts of G. (a) Use the max-flow min-cut theorem to prove that if (S,T) and (S,T) belong to C, then (SS,TT) and (SS,TT) belong to C. Remarks: This part can be solved directly from the definition of a minimumcapacity cut and without reasoning about flows. However, there is a more intuitive argument based on the max-flow min-cut theorem. To receive full credit, your solution is required to be based on the max-flow min-cut theorem. End of remarks. (b) Prove that there is a cut (S,T) in C such that SS for any cut (S,T) in C. Hint: Make use of the result of part (a)