Integer Flow

Now here’s kind of a funny proof. Consider a flow network where all the capacities are integer.

Claim. The maximum flow in this network is integer.

That’s actually fairly obvious from max flow equals min cut: the latter is clearly integer since it is a sum of capacities. How about this though.

Claim. There exists a maximum flow where all the flow values are integer.

That is to say, you don’t have to split flow in an optimal solution. I suppose you might still consider this to be fairly obvious, but it is certainly possible to have optimal flows that are fractional, so how do you prove this? I guess you could try to do some kind of exchange argument to make any flow integer under these circumstances. But here’s a fun alternative.

Proof. The amounts of flow put on an edge by the Ford-Fulkerson algorithm are only ever sums and differences of capacities. The Ford-Fulkerson flow is optimal. Then if all edge capacities are integer, there exists an optimal flow with integer flow on each edge. $\square$

OK, maybe it’s not like laugh out loud funny, but it tickles me. And it’s a generally valid proof strategy to show existence: here is a correct algorithm, and here is a property of its solution, so a solution with this property must exist. This is really just a constructive proof, of course, but we got the algorithm from the literature!

Now the reason I mention this, is it has some interesting consequences over in linear programming. Consider the LP formulation of maximum flow. We now know the optimum is integer and that there exists an optimal solution using only integers – even if we consider the LP to be over the reals (or rationals or whatever). There are actually different ways to know this about the flow linear program, but I digress.