= Solution
The <vertex> version of <Menger's theorem> states that for two distinct nonadjacent <vertices> $s,t$ of a finite <graph>, the <maximum> number of internally vertex-disjoint $s$-$t$ <graph paths> equals the <minimum> size of a <set> $S\subseteq V\setminus\{s,t\}$ whose deletion separates $s$ from $t$.
$$
\boxed{\max\{\text{internally disjoint }s\text{-}t\text{ paths}\}=\min\{|S|:s,t\text{ disconnected in }G-S\}.}
$$
Internally disjoint <graph paths> may share their endpoints but no other <vertex>. The nonadjacency hypothesis is needed in this separator formulation, since an <edge> $st$ cannot be destroyed by deleting other <vertices>.
Back to article page
