# Max-flow-min-cut Theorem explanation behind proof

The theorem states the following:

In any network $(G, s, t, c)$ $(G$ is a directed graph, $s$ is the source, $t$ is the sink, $c$ are the capacities $)$ we have $\sup\{ v(f) : f$ is a feasible flow $\} = \min \{ c(S, T) : (S, T)$ is a cut }$Moreover, the supremum is attained The proof in the lecture notes is attached The problem starts at "Repeating this for each edge, we find a subsequence of flows with$v(f_i) \rightarrow M$such that$f_i(x,y)$converges for each... " If we choose$1$edge, we can find this convergent subsequence, for example by finding a monotone sequence and using standard analysis results. But when we choose the second edge, how do we guarantee that the sequence of flows converges for both of the edges? Thanks in advance ## 1 Answer The trick is a standard analysis one: Let$f_n(x_1y_1)$and$f_n(x_2y_2)$be two sequences. We can then find a subsequence$f_{k_n}(x_1y_1)$which is convergent. Next, instead of looking at$f_n(x_2y_2)$, look at the subsequence$f_{k_n}(x_2y_2)$. This is bounded, thus it has a converegent subsequence$f_{l_n}(x_2y_2)$. Now, since$f_{l_n}(x_1y_1)$is a subsequence of$f_{k_n}(x_1y_1)$it is convergent. Note This is actually an argument about compatcness. In$\mathbb R^d$a set is compact if it is closed and bounded. Thus by boundedness, the sequence $$(f_n(x_1y_1), f_n(x_2y_2),..., f_n(x_dy_d)$$ has a convergent subsequence in some closed ball in$\mathbb R^d\$.

• Oh, i see, thanks a lot! – asdf Dec 26 '17 at 18:06