# find the union of all min cuts of a flow network

I'm trying to solve the following question :

Given a flow network $$N = (G=(V,E),c,s,t)$$. Let $$\mathcal F$$ be the set of all minimum cuts. Prove that $$\mathcal F$$ is closed under intersections and unions, i.e. for every $$S_1,S_2\in\mathcal F , S_1 \cup S_2 \in \mathcal F$$ and $$S_1 \cap S_2 \in \mathcal F$$.

that part I took care of just fine using the min-cut-max-flow theorem.

the other part is the one that I had trouble with :

Given a max flow $$f$$,find $$S_{\min} = \bigcap_{S\in\mathcal F} S \text{ and } S_{\max} = \bigcup_{S\in\mathcal F } S$$.

I realized that when considering a min cut $$(S,T)$$ , and given the residual graph (which can be built from the given maximum flow) , every vertex that's reachable from $$s$$ (source node) , must be in $$S$$ , so I was able to use that to come up with an algorithm to find $$S_{\min}$$.

But as for finding an algorithm for $$S_{\max}$$, I'm kinda having trouble putting my finger on a property of a min cut edge, i.e. what does it take to be a cut edge (or for a vertex to be in $$S$$) of some min cut?

I'm not looking for the full answer but rather a hint.. any help is appreciated.

Note $$S_{\max}=V-\bigcap_{S\in\mathcal{F}}(V-S)$$. And $$\bigcap_{S\in\mathcal{F}}(V-S)$$ is the set of all vertices from which $$t$$ is reachable in the residual graph.
The reason why $$\bigcap_{S\in\mathcal{F}}(V-S)$$ is the set of all vertices from which $$t$$ is reachable in the residual graph is the same as the reason why $$S_{\min}$$ is the set of all vertices that are reachable from $$s$$. You can prove this using the complementary slackness conditions.