Prove that a graph $G$ of order $n \geq 2k$ is $k$ connected if and only if for every 2 disjoint set $V_1$ and $V_2$ of $k$ distinct vertices each, there exist $k$ pairwise disjoint paths connecting $V_1$ and $V_2$
The book told me that I need to start by leting $G$ is a graph of order $n \geq 2k$ such that $G$ is not $k$ connected.
I know that if $G$ is not $k$ connected then the vertex cut $S$ in $G$ will have $k-1$ vertices. $G-S$ will yield many components. I tried to do what I often do for this type of proof is consider the smallest component, says $W$. But I can't spot anything useful about $V_1$ and $V_2$
HINT:
"$\Rightarrow$": $G$ is $k$-connected. Let $V_1$ and $V_2$ be disjoint vertex sets of size $k$. Create $G'$ by adding a vertex $v_1$ and all edges between $v_1$ and $V_1$ and a vertex $v_2$ and all edges between $v_2$ and $V_2$. Now use the expansion lemma (we proved that recently in one of your other questions) to see that $G'$ is $k$-connected. Finish the proof.
"$\Leftarrow$: Assume $G$ has a vertex cut $S$ of size less than $k$. Let $V$ be the smallest component of $G-S$.
Make a vertex set $V_1$ by taking $k$ vertices from $V$ if possible, fill up with vertices of $S$ if necessary.
Make a vertex set $V_2$ by taking $k$ vertices from the other components of $G-S$ if possible, fill up with unused vertices from $S$ if necessary.
Now show that the $k$ disjoint paths between $V_1$ and $V_2$ must meet in $k$ vertices of $S$ to obtain a contradiction.