Given a network N, show that the resultant flow out of the sources is equal to the resultant flow into the sources.

Problem: Let $f$ be a flow in a network $N = (V,X,Y,c)$ with vertice-set $V$, source-set $X$ and sink-set $Y$, and capacity function $c$ . Show that the resultant flow out of the sources is equal to the resultant flow into the sources.

Thoughts: I know the resultant flow out of a sub-set of a network is equal to $f^{out}(X) - f^{in}(X)$ , (the negative of which is the resultant flow into a subset) and so the problem amounts to showing that

$f^{out}(X) - f^{in}(X) = f^{in}(Y) - f^{out}(X)$.

I am stuck and need a hint to progress as I am not sure where to begin.

Observe that we have $$\sum_{v \in V} f^{out}(v) = \sum_{v \in V} f^{in}(v) \tag{1}$$ since the flow on each edge contributes the same amount to both the LHS and the RHS of $(1)$. In addition, by definition of a flow, we have $$f^{out}(v) = f^{in}(v) \quad\text{for } \forall v \not \in X \cup Y \tag{2}$$ By $(1)$ and $(2)$, we then have $$\sum_{v \in X \cup Y} f^{out}(v) = \sum_{v \in X \cup Y} f^{in}(v)$$ Since $X \cap Y = \emptyset$, the conclusion is immediate then.
• @TheMathNoob We have $$\sum_{v \in X}f^{out}(v) + \sum_{v \in Y}f^{out}(v) = \sum_{v \in X}f^{in}(v) + \sum_{v \in Y}f^{in}(v)$$ which implies $$\sum_{v \in X}f^{out}(v) - \sum_{v \in X}f^{in}(v) = \sum_{v \in Y}f^{in}(v) - \sum_{v \in Y}f^{out}(v)$$Note that $$\sum_{v \in X}f^{out}(v) - \sum_{v \in X}f^{in}(v) = f^{out}(X) - f^{in}(X)$$ Similarly for $Y$. – PSPACEhard Apr 5 '17 at 15:41