$G=(V,E)$ be a directed graph with node capacities $\{q_v:v \in V\}$, let $I$ be a set of edges on $V$ disjoint to $E$, let $s,t \in V$, and let $h=\lambda^q_{G+I}(s,t)-\lambda^q_G(s,t)$. Then there is $J \subseteq I$ of size $|J| \geq h$ such that $\lambda^q_{G+\{e\}}(s,t)=\lambda^q_G(s,t)+1$ for every $e \in J$.

Since we consider directed graphs, it is sufficient to prove the lemma for the case of edge-connectivity. For that, apply the following standard reduction that eliminates node capacities: replace every $v \in V \setminus \{s,t\}$ by two nodes $v^{in}, v^{out}$ connected by $q_v$ parallel edges from $v^{in}$ to $v^{out}$ and replace every $uv \in E \cup F$ by an edge from $u^{out}$ to $v^{in}$. Hence we will prove the lemma for the edge connectivity function $\lambda$. Let us say that $S \subseteq V$ is [*tight*]{} if $s \in S$, $v \notin S$, and $|\delta_G(S)|=\lambda_G(s,v)$. Let ${\cal F}$ be the family of tight sets. By Menger’s Theorem ${\cal F}$ is non-empty. It is known that ${\cal F}$ is a ring family, namely, the intersection of all the sets in ${\cal F}$ is nonempty, and if $X,Y \in {\cal F}$ then $X \cap Y, X \cup Y \in {\cal F}$. Then ${\cal F}$ 