0

Given a simple graph (at most one edge between u-v), with no loops or parallel edges, I have to prove that max (s,t) flow is at most O(v^2 / d^2).

I understand that this is asking to prove max flow <= C* (V^2/d^2) for some positivie c. I asked my TA (teacher assistant) and he said that we’d need to prove this by contradiction

MY PROOF

Assume for a contradiction, there’s more than one edge between some vertices x and y. The shortest path is distance ‘d’. I’m stuck after this. In other words, I need to show that the minimum cut cannot be > v^2 / d^2