has a unique inclusion-minimal set $S_{\min}$ and a unique inclusion-maximal set $S_{\max}$. Let $J=\{uv \in I:u \in S_{\min},v \in V \setminus S_{\max}\}$ be the set of edges in $I$ that go from $S_{\min}$ to $V \setminus S_{\max}$. By Menger’s Theorem, $|J| \geq h$, and $\lambda_{G+\{e\}}(s,t)=\lambda_G(s,t)+1$ for any $e \in J$. The statement follows.

Proof of Theorem \[t:main’\] {#s:main'}
============================

Here we prove Theorem \[t:main’\]. All graphs in this and the next section are assumed to be undirected, unless stated otherwise. We start by considering the edge-costs case, and then will show that it implies the node-costs case by reductions.

An ordered pair $\hat{X}=(X,X^+)$ of subsets of a groundset $V$ is called a [*biset*]{} if $X \subseteq X^+$; $X$ is the [*inner part*]{} and $X^+$ is the [*outer part*]{} of $\hat{X}$, and $\Gamma(\hat{X})=X^+ \setminus X$ is the [*boundary*]{} of $\hat{X}$. An edge $e$ covers a biset $\hat{X}$ if it has one endnode in $X$ and the other in $V \setminus X^+$. For a biset $\hat{X}$ and an edge-set/graph $J$ let $\delta_J(\hat{X})$ denote the set of edges in $J$ covering $\hat{X}$.

Given an instance of [SNA]{} and a biset $\hat{X}$ on $V$, let the requirement of $\hat{X}$ be $r(\hat{X})=\max\{r_{uv}: uv \in \delta_D(\hat{X})\}$ 