# Max Flow / Min Cut (undirected graph)

Tags:
1. Mar 30, 2016

### goraemon

1. The problem statement, all variables and given/known data
Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

Designate G = (V, E) as an undirected graph that has at least two vertices. Every edge e on this graph has capacity ce. Pick two arbitrary vertices from G and label them s and t respectively.

Now, we'll let P* be the set of s-t paths in the graph, and let C* be the set of s-t cuts -- meaning, C* refers to the subset of edges in G that constitute all possible s-t cuts.

Demonstrate that the following equality is true:

maxPP* mineP ce = minCC* maxe∈C ce

2. Relevant equations
Size of Max Flow = Min. Capacity of an s-t Cut

3. The attempt at a solution
My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.

Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.

2. Mar 30, 2016

### Ray Vickson

For a given path $P$, the largest flow that can be transmitted along that path equals the smallest arc capacity along the path. This is readily apparent: to send $f$ units of flow along the path, you must send $f$ units along each arc in the path, so $f$ cannot be bigger than the smallest arc-capacity in that path. You can actually achieve a flow equal to the smallest arc capacity, so you have a true minimum, not just a lower bound.