Prove that $G$ has $k$ pairwise disjoint $S$,$T,$ Paths?

Question

Let $G$ be a $k$-connected graph with disjoint sets $S$ and $T$ with at least k vertices.

Prove that $G$ has $k$ pairwise disjoint $S$,$T,$ Paths

So, I have seen some solutions to this question, but there are few things I do not really understand.

Proof begins with

Let $x$ and $y$ be two vertices such that $x$ is adjacent to all vertices in $S$ and $y$ is adjacent to all vertices in $T$.

Then, by expansion lemma, New graph, $G'$ is still k-connected.

1. By menger's theorem, there exists at least k pairwise internally disjoint paths between x and y

-> Menger's theorem says that for $x,y \in V(G)$ and $xy \notin E(G) $, minimum size of an $x,y$-cut equals the maximum number of pairwise internally disjoint $x,y$-paths

From this theorem, how can I say that there exists at least $k$ pairwise internally disjoint paths between $x$ and $y$?

2. Then, Remove $x$ and $y$ from each of these paths to get the required paths.

So, if there exists at least $k$ internally disjoint paths, how can I complete the proof by deleting $x$ and $y$?

Thanks.

Answer 1

Menger's theorem says that for $x,y \in V(G)$ and $xy\notin E(G)$, minimum size of an $x,y$-cut equals the maximum number of pairwise internally disjoint $x,y$-paths.

From this theorem, how can I say that there exist at least $k$ pairwise internally disjoint paths between $x$ and $y$?

The graph $G'$ is $k$-connected. In particular, the minimum size of an $x,y$-cut in $G'$ is at least $k$, because if we need to delete at least $k$ vertices to disconnect the graph in any way, we definitely need to delete at least $k$ vertices to disconnect the graph in a way that separates $x$ from $y$.

Since the minimum size of an $x,y$-cut is at least $k$, the number of pairwise internally disjoint $x,y$-paths is at least $k$, by Menger's theorem.

Then, remove $x$ and $y$ from each of these paths to get the required paths.

So, if there exist at least $k$ internally disjoint paths, how can I complete the proof by deleting $x$ and $y$?

Each of the internally disjoint $x,y$-paths starts at $x$ and ends at $y$. Let $v_0, v_1, v_2, \dots, v_\ell$ be the vertices of one such path, with $v_0 = x$ and $v_1 = y$.

Since $x$ is only adjacent to vertices in $S$, we know that $v_1 \in S$. Since $y$ is only adjacent to vertices in $T$, we know that $v_{\ell-1} \in T$.

So if we delete $v_0$ and $v_\ell$ from the path, we get a path from $v_1$ to $v_{\ell-1}$: a path from a vertex in $S$ to a vertex in $T$.

When we do this to every path, we get $k$ pairwise disjoint paths from $S$ to $T$. (Our paths started out pairwise internally disjoint, so they shared no vertices except their first and last vertex. But we got rid of the first and last vertex of every path, so now they don't share any vertices.)