Applying Menger's theorem to a 2-connected graph to show there exist $k$ pairwise disjoint S,T paths

Question

Let G be a 2-connected graph. S,T are disjoint subsets of V(G) with size at least $k$. Show that there exists $k$ pairwise disjoint S,T-paths.

My current solution: Add a vertex $x$ adjacent to each vertex in S, and add a vertex $y$ adjacent to every vertex in T. To Be Determined ...

Can I apply Menger's theorem here? If so, how?

Answer 1

Might as well post it as an answer. See my comment for why $2$-connectedness isn't sufficient.

Let $G$ be a k-connected graph. $S,T$ are disjoint subsets of $V(G)$ with size at least $k$. Show that there exists $k$ pairwise disjoint $S,T$-paths.

Add a vertex $x$ adjacent to each vertex in $S$, and add a vertex $y$ adjacent to every vertex in $T$.

$x$ and $y$ are both adjacent to at least $k$ vertices, so the new graph is $k$-connected.

By Menger's theorem there exist at least $k$ internally disjoint paths from $x$ to $y$.

Say one of these paths is $xv_1 \ldots v_ny$. Let $v_j$ be the first of these vertices that is in $T$ and $v_i$ be the last of these vertices that is in $S$ such that $i<j$. Then $v_i \ldots v_j$ is an $S,T$-path.

We can do this to each of the $\geq k$ paths. Since the original paths were internally disjoint, the reduced paths must be disjoint as required.