Instance of Ford Fulkerson violating property
Somehow I created this graph which seems to violate one of the properties that the value of flow is upper bounded by the capacity of min cut.
Here's the graph:
Max flow that the algorithm finds is 7. (sending 3 on s-a-c-t, 3 on s-b-t and 1 on s-a-t)
While the min-cut in the graph is {s,b} , {a,c,t} with capacity 5.
I'm not sure where I'm going wrong in this. Can someone please correct this?
The value of a cut is the sum of the capacities of the edges that are "cut".
In the case with cutting the graph into {s,b} and {a,c,t}, the edges are s-a, b-t, (and you can count a-b if you want), which means the value is 8 (11 if you count a-b), not 5.
As far as I can tell, the min cut would include the edges a-t, b-t, and c-t, which has a value of 7, which is consistent with Ford-Fulkerson.