# Why is this flow a max flow?

According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how can this be the max flow?

• How could there be any flow from $s$ to $t$ if there were no paths for it to flow along? – David Richerby Jun 5 '15 at 8:37
• Visually this is also easy to see. Notice the links a->b and c->d, these are the only connections from the left side to the right side, and they are fully utilized. I.e. it is a max flow. – Bjarke Freund-Hansen Jun 10 '15 at 8:11

You've left out part of the statement. It should be "If there's no path between the source and the sink with unused capacity the flow is a max flow." If you look at your graph you'll see that there is no path with unused capacity all the way from $s$ to $t$. The $s$ to $a$ link has spare capacity but $a$'s lone outbond link is saturated. The $s$ to $c$ link is saturated.

if there was no path from s to t, then the flow would be a max flow.

The correct statement is,

if there is no path from $s$ to $t$ in the residual network, then the flow is a max flow.

If you build the residual network, you'll see that there is no edge from $a$ to $b$ and none from $c$ to $b$ or $d$, so $s$ and $t$ are disconnected.

The flow is maximum if there is no augmenting(i.e. improving) path between s and t. A path would contribute to the maximum flow if all its edges have strictly positive capacity left. In your case although you have some paths between s and t, all of them will have at least one edge that has used its whole capacity. Thus you can't improve the current flow and it is maximum.

• It adds at least one term and it touches on the intuitive part of the theorem. I believe my answer makes it more clear why the theorem is true, not just what is the theorem – Ivaylo Strandjev Jun 5 '15 at 12:27

You need to draw the residual network for this.The augmented path finding procedure should be done in the residual network.

There are no augmented path from S to t here. So this is a max flow.