## 3 Stable Flows
This means that none of the \(v^{in}v^{out}\) edges are blocking, so either \(g(v^{in}v^{out})=p(v^{in}v^{out})=q(v)\) or \(v^{in}v^{out}\) must be \(g\)-dominated at \(v^{out}\); hence, \(v^{out}\) is assigned to a \(q(v^{out})=q(v)\) amount of allocation. As \(q(v)\) is more than the total capacity of arcs leaving \(v\), \(g(v^{in}v^{out})>0\) or \(g(v^{out}v^{in})>0\) must hold. Therefore, \(v^{out}\) must have exactly a \(q(v)\) amount of allocation whenever \(v^{in}v^{out}\) is present. An exchange of \"\(in\)\" and \"\(out\)\" shows that the presence of \(v^{out}v^{in}\) implies that \(v^{in}\) has exactly \(q(v^{in})=q(v)\) allocation. These observations directly imply that [PERSON]'s law holds for \(f\) at each node different from \(s\) and \(t\). The capacity condition is also trivial for \(f\); hence, \(f\) is indeed a flow of \(D\). Observe that by the choice of \(q\), neither \(s\) nor \(t\) is \(g\)-saturated; hence, no edge is \(g\)-dominated at \(s\) or at \(t\). Assume that walk \(P=(v_{1},v_{2},\ldots,v_{k})\) blocks flow \(f\). As \(P\) is \(f\)-unsaturated, each edge \(v_{i}^{out}v_{i+1}^{in}\) of \(G_{D}\) must be \(g\)-dominated at \(v_{i}^{out}\) or at \(v_{i+1}^{in}\). Walk \(P\) is blocking; hence, either \(v_{1}\) is terminal, and hence, \(v_{1}^{out}v_{2}^{in}\) cannot be dominated at \(v_{1}\) or there is a \(v_{1}u\) arc with a positive flow value, such that \(v_{1}u>_{v_{1}}v_{1}v_{2}\). In both cases, edge \(v_{1}^{out}v_{2}^{in}\) has to be \(g\)-dominated at \(v_{2}^{in}\). This means that \(g(v_{2}^{in}v_{2}^{out})>0\). As arc \(v_{2}v_{3}\) is \(f\)-unsaturated, it follows that edge \(v_{2}^{out}v_{3}^{in}\) must be \(g\)-dominated at \(v_{3}^{in}\). This yields that \(g(v_{3}^{in}v_{3}^{out})>0\). Again, arc \(v_{3}v_{4}\) is \(f\)-unsaturated; hence, edge \(v_{3}^{out}v_{4}^{in}\) has to be \(g\)-dominated at \(v_{4}^{in}\), and so on. At the end, we get that \(v_{k-1}^{out}v_{k}^{in}\) is \(g\)-dominated at \(v_{k}^{in}\). As terminal vertices \(s\) and \(t\) are \(g\)-unsaturated, \(v_{k}\) cannot be a terminal vertex. Therefore, by the blocking property of \(P\), there is an arc, \(wv_{k}\), with a positive flow and \(v_{k-1}v_{k}<_{v_{k}}wv_{k}\); hence, again, \(v_{k-1}^{out}v_{k}^{in}\) cannot be \(g\)-dominated at \(v_{k}^{in}\). The contradiction shows that no walk, \(P\), can block \(f\). Assume now that \(f\) is a stable flow of \(D\). We have to exhibit a stable allocation, \(g\), of \(G_{D}\), such that \(f\) is the \"restriction\" of \(g\). Define \(g(u^{out}v^{in}):=f(uv)\), so we only need to determine the \(g(v^{in}v^{out})\) and \(g(v^{out}v^{in})\) values for all nonterminal vertices, \(v\). Actually, the stable allocation that we look for might not be unique. In what follows, we shall construct a particular one, the so-called _canonical representation_, \(g_{f}\), of \(f\). Let \(S\) be the set of those vertices, \(u\), of \(D\), such that there exists an \(f\)-unsaturated directed walk \(P=(v_{1},v_{2},\ldots,v_{k}=u)\) that is not \(f\)-dominated at \(v_{1}\). As no walk can block \(f\), \(S\) is disjoint from terminal vertices \(s,t\). To determine \(g_{f}\), for each nonterminal vertex, \(v\), allocate the remaining quota of \(v\) to \(v^{in}v^{out}\) or to \(v^{out}v^{in}\), depending on whether \(v\in S\) or \(v\
ot\in S\) holds. More precisely, define:  
\[g_{f}(v^{in}v^{out}) = \left\{ \begin{array}{ll}q(v)-\sum_{x\in V(D)}f(vx)&\mbox{ if }v\in S \\ 0&\mbox{ if }v\
ot\in S\end{array} \right.\mbox{ and } \tag{18}\] \[g_{f}(v^{out}v^{in}) = \left\{ \begin{array}{ll}q(v)-\sum_{x\in V(D)}f(xv)&\mbox{ if }v\
ot\in S \\ 0&\mbox{ if }v\in S\end{array} \right. \tag{19}\]  
By the definition of \(q\), both \(g_{f}(v^{in}v^{out})\) and \(g_{f}(v^{out}v^{in})\) are nonnegative. If \(v\in S\), then the amount of total allocation of \(v^{out}\) is \(q(v)=q(v^{out})\) by Equation (18), and for \(v\
ot\in S\), the amount of total allocation of \(v^{in}\) is \(q(v)=q(v^{in})\) by Equation (19).