= Solution
{c}
Add two new <vertices> $s,t$ to $G$, joining $s$ to every <vertex> of $U$ and $t$ to every <vertex> of $W$, with no other new <edges>. The <vertices> $s,t$ are nonadjacent. Suppose $S\subseteq V(G)$ has $|S|<k$. Since $G$ is a <k-connected graph>, $G-S$ is a <connected graph>. Both $U\setminus S$ and $W\setminus S$ are nonempty because each original <set> has <cardinality> $k$. Choose $u\in U\setminus S$ and $w\in W\setminus S$; a <graph path> between them in $G-S$ extends to an $s$–$t$ <graph path> avoiding $S$.
Consequently no fewer than $k$ <vertices> can form an $s$–$t$ <vertex separator>. By <Menger's theorem>, there are at least $k$ <internally vertex-disjoint paths> from $s$ to $t$. There cannot be more than $k$, since $s$ has only $k$ <neighbours>.
Remove $s,t$ from these $k$ <graph paths>. The resulting <graph paths> in $G$ start at distinct <vertices> of $U$, end at distinct <vertices> of $W$, and are pairwise <vertex-disjoint paths>: any shared <vertex> would have been an internal <vertex> common to two of the original <graph paths>. Because there are exactly $k$ <graph paths>, they use every <vertex> of $U$ and $W$ as an endpoint. None can pass through another terminal internally, since that terminal already occurs as an endpoint of one of the <vertex-disjoint paths>. Thus there are $k$ <vertex-disjoint paths> from $U$ to $W$, with some pairing of the endpoints. This is also an immediate application of the <Set version of Menger theorem>.
Back to article page
