Can a flow graph with integer capacities have an edge with a non-integer flow in its maximum flow?

Question

Restating the problem a bit: We have a flow graph, G, with integer capacities. Can we find a maximum flow where for at least one of the edges, e, we have f(e) equal to a non-integer?

The first time I tried this I kind of glossed over it and thought that this violated the Integrality Theorem and therefore that it was false, but reading it carefully after makes it clear that it does not break any rules. Apparently it is true.

I've been trying to draw up a simple example to get a visualization, but I can't seem to come up with anything. Can anyone show me an example flow graph where this works?

Answer 1

Yes, it is possible for a maxflow to have non-integer flows on edges with graphs having all integer capacities. Refer to the image. The values in boxes are the flows and the numbers without boxes are capacities.

PS : Remember that a graph with integer capacities will always have a integer maxflow value. But it does not rule out the possibility of max flow with non-integer flows on edges.

Answer 2

By applying the Ford Fulkerson algorithm, all flow values and all residual capacities remain integer throughout the execution. This means that there exist at least one flow only with integer components.