Max Flow Min Cut Question

Question

Hello!

I'm trying to prove that for any given edge along a minimum cut in a flow network, the capacity of that edge is equal to the flow along that edge. Basically, if you take any edge on a minimum cut, the flow going through that edge is at maximum capacity. It's easy to verify this with some examples and seems pretty intuitive since we know that the sum of the capacities along a min cut is equal to the max flow. But I'm stuck on how I could prove this claim.

My first thought was a proof by contradiction: Assume we have a minimum cut such that there exists an edge e in which f(e) < c(e). And show why this cant be. But I'm running into some trouble with it and I'm not sure if this is the right route. Any suggestions would be really appreciated!

Answer 1

Just use your statement

"the sum of the capacities along a min cut is equal to the max flow".

If the flow on any edge were smaller than its capacity then some other edge

on the min cut would need to compensate by having a flow larger than its capacity.