I am going through the proof of the max-flow min-cut theorem presented in the following paper: Ford, L., & Fulkerson, D. (1956). Maximal Flow Through a Network. Canadian Journal of Mathematics, 8, 399-404. doi:10.4153/CJM-1956-045-5
There is one concept I don't quite fully understand, the average of maximal flows and particularly, its impact on the level of saturation for each arc. For example, during the proof of the following lemma:
$\textbf{Lemma 1.}$ $S$ is a disconnecting set, where
- $S$ is the class of all arcs that are saturated in every maximal flow.
- A disconnecting set is a collection of arcs that has the property that every chain (i.e., path) joining the source and sink meets the collection.
$\textbf{Proof.}$ Suppose for contradiction $S$ is not a disconnecting set. Then there exists a chain $\alpha_1,\alpha_2, \cdots, \alpha_k$ joining the source $s$ and the sink $t$ with $\alpha_i \notin S, \forall i$. Hence, corresponding to each $\alpha_i$ there is a maximal flow $f_i$ in which $\alpha_i$ is unsaturated. But the average of these flows
$\begin{equation} f= \frac{1}{k} \sum_{i=1}^{k} f_i \end{equation}$
is maximal and $\alpha_i$ is unsaturated by $f$ for each $i$.
$\textbf{My Question:}$
How did we come to the conclusion that "$\alpha_i$ is unsaturated by $f$ for each $i$"? I came across the explanation by @Guyslain in Disconnecting set in the maximal flow problem but I don't understand the last equation:
$$0 \leq f(\alpha_j) = \frac{1}{k} \sum_{i=1}^k f_i(\alpha_j) < \frac{1}{k} \sum_{i=1}^{k} c(\alpha_j) = c(\alpha_j)$$
We know by definition that $f_i(\alpha_i) < c(\alpha_i)$ but does this also apply to $\alpha_j$ such that $f_i(\alpha_j) < c(\alpha_j)$, $\forall j\in[1,k]\backslash i$?
Considering the arc $\alpha_j$, $f_j(\alpha_j) < c_i$ indeed, and we do not have in general a strict inequality for the other flows, we only know that $f_i(\alpha_j) \leq c_i$. But it does not matter: when summing inequalities, it is enough to have one inequality strict for the sum to be a strict inequality. This implies that $\frac{1}{k} \sum_{i=1}^k f_i(\alpha_j) < c_j$.