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
When you prove something by contradiction, you assume the negation of the statement you're proving. You would assume for contradiction that there's more than one edge between some pair of vertices if your goal was to prove that the graph was simple.
But that's not what's happening here. It's one of your assumptions that the graph is simple. In a proof by contradiction, here, you would want to assume that the max flow is not $O(v^2/d^2)$.
In fact, a proof by contradiction isn't necessary here. To prove that the max flow is at most some upper bound $x$, it's equivalent to prove that the min cut is at most some upper bound $x$. To do that, it's enough to find some cut, not necessarily the min cut, with capacity $x$. (Then, the min cut can only be lower than that!)
So, your goal is to prove that if the distance between $s$ and $t$ is $d$, then there is a cut of capacity $O(v^2/d^2)$.
Here's a sketch of an argument. Let $V_1, V_2, \dots, V_{d-1}$ be the sets of vertices at distance $1, 2, \dots, d-1$ from $s$, respectively. Then for every $i$ such that $1 \le i < d-1$, deleting all the edges between $V_i$ and $V_{i+1}$ will disconnect $s$ from $t$, so it corresponds to a cut.
The "average case" is that $V_1, V_2, \dots, V_{d-1}$ all have size about $\frac{v}{d-1}$. The number of edges between $V_i$ and $V_{i+1}$ is at most $|V_i| \cdot |V_{i+1}|$, which would be about $(\frac{v}{d-1})^2$.
You cannot guarantee that you're in the average case, of course. But you should be able to argue that at least one of these cuts is not much worse than average, proving the result you want.