Unnumbered Eqs.(29)–(32),(145): Steiner-cut LP identity

For all natural numbers $n,e$, consider a graph $G$ on vertices $\{0,\ldots,n-1\}$ with edges $\{0,\ldots,e-1\}$, distinct designated endpoints $L(a),R(a)$ for each edge, and the property that edges with identical endpoints in either order are equal; let $c_a\ge0$ be real capacities and let $S$ be a vertex set with $|S|\ge2$. For a real assignment $f_{a,b}$, with $b\in\{0,1\}$, define

For vertices $u,v$, call $f$ feasible for $(u,v)$ when all its entries are nonnegative, $f_{a,0}+f_{a,1}\le c_a$ for each edge, and $D_f(w)=0$ at every $w\ne u,v$; let $V_{u,v}$ be the supremum of the source outflows $D_f(u)$ of these feasible assignments. Let $\mathcal T=\{(u,v)\in S\times S:u<v\}$, and let $K$ be the supremum of all real $z$ for which there is a family $(f_p)_{p\in\mathcal T}$ such that each $f_{(u,v)}$ is feasible for $(u,v)$ and $z\le D_{f_{(u,v)}}(u)$; these capacity bounds hold separately for each pair, with no capacity sum across pairs. For any vertex set $A$, let $C(A)$ be the sum of $c_a$ over edges with exactly one endpoint in $A$, call $A$ a terminal-separating cut when there exist $u,v\in S$ with $u\in A$ and $v\notin A$, and let $H$ be the infimum of the capacities of all such cuts. Then all four assertions hold: $H=K$; there exists $p=(u,v)\in\mathcal T$ with $V_{u,v}=K$ and $V_{u,v}\le V_{u',v'}$ for every $(u',v')\in\mathcal T$; there exists a terminal-separating cut $A$ with $C(A)=H$ and $C(A)\le C(B)$ for every terminal-separating cut $B$; and there exists a family $(f_p)_{p\in\mathcal T}$ of the stated separately feasible assignments with $K\le D_{f_{(u,v)}}(u)$ for every $(u,v)\in\mathcal T$. The cardinality hypothesis excludes $n<2$, but empty edge sets, zero capacities, and disconnected terminal pairs are permitted.