# Maximum flow minimum cut

For the following problem I am trying to find maximum flow and minimum cut:

I found the maximum flow as 6 like this:

$$1-3-7-8:2 flows$$

$$1-2-5-8: 2 flows$$

$$1-3-4-5-8:1 flow$$

$$1-3-4-6-5-8:1 flow$$

But I am having trouble to match the min cut, I thought it would be 8(by cutting the following arcs $$(7,8)$$ and $$(5,8))$$. How do I match the min cut? Or do you think I made a mistake finding max flow?

The maximum flow is $$6$$. To find a corresponding minimum cut, note that $$S=\{1,3,4,7\}$$ is the set of nodes reachable from the source node $$1$$ in the residual network. Now consider the arcs from $$S$$ to $$N\setminus S$$.
• Yes, those are correct, with sum of capacities equal to $2+1+1+2=6$, matching the flow value. Jan 22 at 21:49