= Solution
For nonadjacent vertices $a,b$, the <local connectivity> $\kappa(a,b;G)$ is the minimum cardinality of an $a$-$b$ <vertex separator>: a set $S\subseteq V(G)\setminus\{a,b\}$ such that $a$ and $b$ lie in different components of $G-S$.
To prove the vertex form of the <Menger theorem>, replace every vertex $v\notin\{a,b\}$ by an arc $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of capacity one. Replace every undirected edge $uv$ by directed arcs from $u_{\mathrm{out}}$ to $v_{\mathrm{in}}$ and conversely, each of capacity larger than $|V(G)|$; leave $a,b$ unsplit. An integral $a$-$b$ flow of value $k$ decomposes into $k$ paths, and the unit-capacity vertex arcs force the corresponding graph paths to be <internally vertex-disjoint paths>. Conversely, $k$ such paths give an integral flow of value $k$.
Because $a$ and $b$ are nonadjacent, any finite minimum cut consists entirely of unit-capacity vertex arcs. These arcs correspond exactly to an $a$-$b$ vertex separator of the same size. The <max-flow min-cut theorem>, whose augmenting-path proof also guarantees an integral maximum flow for integral capacities, therefore gives
$$
\max\{\text{number of internally vertex-disjoint $a$-$b$ paths}\}
=\kappa(a,b;G).
$$
In particular, $G$ contains the required set of $\kappa(a,b;G)$ paths.
Back to article page
