# a graph $G$ of order $n \geq 2k$ is $k$ connected iff there exist $k$ pairwise disjoint paths connecting $V_1$ and $V_2$

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$

• "disjoint paths" means that they have no vertexes or no edges in common? Oct 10, 2014 at 14:55

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.

• for => direction, do I need to connect $v_1$ and $v_2$, because they said "$k$ pairwise disjoint paths connecting V1 and V2" meaning $V_1$ and $V_2$ has to be connected to each other, right? Or I understand it incorrectly again? Oct 11, 2014 at 13:17
• You understand it correctly. After concluding that $G'$ is $k$-connected you find $k$ internally disjoint paths between $v_1$ and $v_2$ in $G'$ and these translate to $k$ disjoint paths between $V_1$ and $V_2$ in $G$. (I edited "disjoint" into the answer). Oct 11, 2014 at 15:29
• Thank you very much, I'm much appreciated. Oct 11, 2014 at 16:02
• Lol, you are clearly about as English as I am. Have this translated and you will laugh :) Oct 11, 2014 at 16:54