Max flow min cut in matching reduced to max flow

Question

I can not find the max flow, min cut in this graph where all edges have capacity 1.

The graph: 1

The max flow in this graph from s to t is 2? But it is impossible to separate s and t without cutting atleast 3 edges?

Answer 1

If you apply the usual flow-augmenting algorithm, you may arrive at flows of 1 in each of the arcs sa, sb, ab', ba', a't, and b't, flows of zero in the other arcs, so there's your flow of value 2. Now when you run the flow-augmenting algorithm again, you can label the source, s, and you can label c from s, and you can label b' from c, and (the tricky part) you can label a from b' (since b' is labeled, a is unlabeled, and there is a flow from a to b). So the cut is $A=\{\,s,c,b',a\,\},B=\{\,b,a',c',t\,\}$, and the arcs from $A$ to $B$ are sb and b't, and cutting those two arcs indeed separates s from t.