I am having trouble with the following alteration to a max flow problem.
If I have a directed graph $G(V,A)$ with arc capacities $c_i$ and a source/sink. Suppose $f$ is the max flow within $G$, is $f$ still a max flow in G with $c^{'}$ if we define the following as $c_i^{'} = c_i$ $\forall$ arcs with $f_i = c_i$ and $c_i^{'} = c_i + 1$ $\forall$ arcs with $f_i < c_i$?
I have tried to consider ford-fulkerson with the condition to try and show that they're the same. It could be that it is false as well
Here we use the term network flow and flow network interchangeably. The newer capacities $c'$ are the same as in the original network flow for edges carrying saturated flow and they are one more than the original capacity for edges that doesn't carry saturated flow. Consider all cuts (A,B) of the network flow, we can denote a min-cut of the network flow by (A*,B*). We can say that after we adjusted the capacities of the edges to the new capacities, the new capacity of any (A,B) cuts will be bigger than or equals to old capacity of the (A,B) cut. The minimum (A,B) cut in newer capacity setting could not have decrease from the capacity of the old min-cut. So by the max-flow min-cut theorem, the newer maximum flow, which is equals to the capacity of the newer min-cut, is greater than or equals to the capacity of the old min-cut which is the max-flow of the old network flow.
So we know therefore that the newer max-flow is at least as much as the old max-flow. What we want to know is that is it possible that the newer max-flow is larger than the older max-flow.
Consider the Min-cut $(A^*,B^*)$ that was picked above from the network flow, given a maximum flow of the network, all the edges carrying flow out of $A^*$ will be saturated and so the capacity of the edges going out of the min cut $(A^*,B^*)$ will not be increased for the newer capacities. So the min-cuts for the newer network flow is the same as the min-cut for the old network flow because any other cuts in the newer network flow is going to have larger capacities than the capacity of the min-cut in the original network flow.
This is very easy to understand, we sort the capacities of the cuts in an ascending fashion like this $C_{min1} \leq C_{min2} <C_1<C_2<...<C_{max1}\leq C_{max2} \leq...\leq C_{maxm}$. In the newer network flow, the capacity of the cuts could be increased but the capacity of the min-cuts stays the same. Therefore, again, the capacity of the min-cut in the newer network flow is still the same as the capacity of the min-cut in the original network flow. Hence, by the max-flow min-cut theorem, the max flow of the newer network flow is the same as the min=cut of the newer network flow, which is the same as the min-cut of the original network flow which is equals to the original max-flow.