Flow Value and Source-Sink Balance

Flow Value Measures Net Transfer

A feasible flow assigns an amount to each directed edge, subject to capacity limits and conservation at vertices other than the source and sink. To describe how much the flow transfers from source to sink, we need a single number. The correct quantity is not necessarily the total flow on edges leaving the source: some flow may also enter it. The flow value is the net amount leaving the source.

Throughout, a network is a finite directed graph $G=(V,E)$ with distinct designated vertices $s$ and $t$, called the source and sink, and a capacity function $c:E\to[0,\infty)$. Each directed edge $e$ has a flow amount $f(e)$. Oppositely directed edges, when both are present, are separate edges and are counted separately. There are no loops. A feasible flow satisfies $0\le f(e)\le c(e)$ for every edge, and at every vertex $v\notin\{s,t\}$, total incoming flow equals total outgoing flow. No conservation condition is imposed at $s$ or $t$.

Definition: For a vertex $v$, its net flow out is the total flow on edges directed out of $v$ minus the total flow on edges directed into $v$. The value of a feasible source-sink flow $f$ is its net flow out of the source: $$ |f|=\sum_{\substack{e\in E\\ e\text{ leaves }s}} f(e) -\sum_{\substack{e\in E\\ e\text{ enters }s}} f(e). $$

The notation $|f|$ denotes a signed net amount, not an absolute value. Under the stated feasibility conditions alone, it can be negative: those conditions do not rule out a net flow from $t$ toward $s$. In the common case that no flow enters $s$, the value is simply the sum of the flows leaving $s$. The corresponding statement at the sink is that the value equals the total flow entering $t$ minus the total flow leaving $t$.

Why Source and Sink Balances Agree

For each vertex $v$, write $b_f(v)$ for its net flow out. Thus outgoing edges contribute positively to $b_f(v)$, and incoming edges contribute negatively. At every internal vertex, conservation says $b_f(v)=0$. At the source, $b_f(s)=|f|$. The balance at the sink is not an independent choice: it is determined by the other balances.

Lemma (Global balance identity): For any assignment of flow amounts to the directed edges of a finite graph, $$ \sum_{v\in V} b_f(v)=0. $$

Proof. Consider one directed edge $e=uv$ carrying amount $f(e)$. In the sum over all vertices, this amount contributes $+f(e)$ to $b_f(u)$, because it leaves $u$, and $-f(e)$ to $b_f(v)$, because it enters $v$. Its total contribution is $f(e)-f(e)=0$. Summing these zero contributions over every edge gives $\sum_{v\in V}b_f(v)=0$. This argument also covers a graph with no edges, when the sum has no edge contributions and equals zero. $\square$

Theorem (Source-sink balance): In a feasible flow on a network with source $s$ and sink $t$, the value is the net flow into the sink: $$ |f|=\sum_{\substack{e\in E\\ e\text{ enters }t}}f(e) -\sum_{\substack{e\in E\\ e\text{ leaves }t}}f(e). $$

Proof. Separate the vertices into $s$, $t$, and the internal vertices $V\setminus\{s,t\}$. By the global balance identity, the sum of $b_f(v)$ over all vertices is zero. Each internal vertex has balance zero by feasibility, and $b_f(s)=|f|$ by definition. Therefore $0=|f|+b_f(t)$, so $b_f(t)=-|f|$. The net flow into $t$ is the negative of its net flow out, namely $-b_f(t)$, and hence equals $|f|$. If there are no internal vertices, the internal sum is empty and equals zero, so the same calculation applies. $\square$

The theorem does not assert that gross outgoing flow at the source equals gross incoming flow at the sink in every network. It asserts equality of the two net quantities. This distinction matters whenever edges carry flow into the source or out of the sink.

Calculating Flow Values

Worked Example: A Network with No Flow Entering the Source

Let $V=\{s,a,b,t\}$, with directed edges $s\to a$, $s\to b$, $a\to b$, $a\to t$, and $b\to t$. Their capacities and assigned flows are, respectively, $6,5$; $5,4$; $3,2$; $4,3$; and $8,6$, where each pair lists capacity first and flow second. The source is $s$ and the sink is $t$.

First check the capacity condition on every edge: $5\le6$, $4\le5$, $2\le3$, $3\le4$, and $6\le8$; every flow amount is also nonnegative. At $a$, the incoming amount is $5$, and the outgoing amount is $2+3=5$. At $b$, the incoming amount is $4+2=6$, and the outgoing amount is $6$. Thus conservation holds at both internal vertices.

There is no edge entering $s$. The total flow leaving it is $5+4=9$, so $|f|=9-0=9$. At $t$, the total incoming flow is $3+6=9$, and no flow leaves. Its net inflow is $9-0=9$, agreeing with the theorem.

Check: Summing the internal balances and the two terminal balances gives $b_f(s)=9$, $b_f(a)=0$, $b_f(b)=0$, and $b_f(t)=-9$. Their sum is $9+0+0-9=0$, as required by the global balance identity.

Worked Example: Incoming Flow at the Source

Let $V=\{s,a,t\}$, with directed edges $s\to a$, $a\to s$, $a\to t$, and $s\to t$. Their capacities and flows are, respectively, $7,5$; $3,2$; $5,3$; and $6,4$. The source is $s$ and the sink is $t$.

The capacity checks are $5\le7$, $2\le3$, $3\le5$, and $4\le6$, and all amounts are nonnegative. At the only internal vertex $a$, the incoming amount is $5$, while the outgoing amount is $2+3=5$. Thus the assignment is feasible.

At the source, the outgoing amount is $5+4=9$, but the incoming amount is $2$. The value is therefore $9-2=7$, not $9$. At the sink, the incoming amount is $3+4=7$, and its outgoing amount is $0$, so its net inflow is $7-0=7$. The two net values agree.

Check: The vertex balances are $b_f(s)=9-2=7$, $b_f(a)=5-5=0$, and $b_f(t)=0-7=-7$. Their sum is $7+0-7=0$. This also shows why counting only the edges leaving the source would give the wrong value in this network.

Circulations and Flow Value

A circulation is a flow assignment for which incoming flow equals outgoing flow at every vertex, including the source and sink. A circulation can place positive amounts on edges while having net balance zero everywhere. More generally, a flow may contain a circulation in addition to its source-to-sink transfer. The local amounts on edges can then be larger than the net amount transferred.

Worked Example: A Circulation Alongside Source-to-Sink Flow

Let $V=\{s,a,b,t\}$, with directed edges $s\to a$, $a\to t$, $a\to b$, and $b\to a$. Their capacities and flows are, respectively, $4,3$; $4,3$; $3,2$; and $3,2$. The source is $s$ and the sink is $t$.

For each edge, the capacity check is $3\le4$, $3\le4$, $2\le3$, and $2\le3$; every assigned amount is nonnegative. At $a$, the incoming amount is $3+2=5$, from $s$ and $b$, and the outgoing amount is $3+2=5$, to $t$ and $b$. At $b$, the incoming amount is $2$ and the outgoing amount is $2$. The flow is feasible.

At $s$, the outgoing amount is $3$ and the incoming amount is $0$, so $|f|=3-0=3$. At $t$, the incoming amount is $3$ and the outgoing amount is $0$, so the net inflow is $3-0=3$. The two opposing edges between $a$ and $b$ carry $2$ units in each direction. Their contributions to each vertex's net balance cancel: at $a$ they contribute $+2-2=0$, and at $b$ they contribute $+2-2=0$.

Check: The balances are $b_f(s)=3$, $b_f(a)=(3+2)-(3+2)=0$, $b_f(b)=2-2=0$, and $b_f(t)=0-3=-3$. Their sum is $3+0+0-3=0$. The circulation uses $2$ units on each of its two edges, but it adds zero to the source-sink value.

Common Mistake: Counting Gross Outflow

A frequent error is to define the value as the sum of all flow leaving $s$, without subtracting flow entering $s$. In the second example, that calculation gives $5+4=9$. It is incorrect because $2$ units enter the source; the net amount leaving is $9-2=7$. The sink calculation confirms the correction: $3+4=7$ units enter $t$, and none leave, so the net inflow is $7$.

The same issue arises at the sink if some edges leave $t$. In that case, the amount entering $t$ alone is not its net inflow: subtract the amount leaving $t$. The source-sink balance theorem compares net outflow at the source with net inflow at the sink, not gross totals.

When calculating a flow value, use a consistent three-part check:

List every edge directed out of the source and add its flow.
List every edge directed into the source and subtract its flow.
Independently calculate net inflow at the sink and compare the results.

Conservation at internal vertices is what makes the comparison work. The proof does not require capacities to be integers, positive, or equal; it uses only finite sums of edge amounts and conservation at every vertex other than $s$ and $t$. Capacity constraints are essential for feasibility, but they do not alter the balance identity.

Check Your Understanding

For each proposed flow, check the stated capacity and conservation conditions before calculating its value.

In the first worked example, what is the flow value if the amount on $s\to b$ is changed from $4$ to $3$ and all other amounts remain unchanged? Does the resulting assignment still satisfy conservation at $b$?
A source has outgoing flow amounts $8$ and $5$, and incoming flow amount $4$. What is its net outflow?
At a sink, $11$ units enter and $3$ units leave. What is its net inflow, and what must the source flow value be in a feasible network?
Explain why the two equal flows on $a\to b$ and $b\to a$ in the third example do not change the value.
Why does the source-sink balance proof still work when $V=\{s,t\}$ and there are no internal vertices?