3
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ "disjoint paths" means that they have no vertexes or no edges in common? $\endgroup$
    – Exodd
    Oct 10, 2014 at 14:55

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Oct 11, 2014 at 13:17
  • $\begingroup$ 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). $\endgroup$ Oct 11, 2014 at 15:29
  • $\begingroup$ Thank you very much, I'm much appreciated. $\endgroup$ Oct 11, 2014 at 16:02
  • 1
    $\begingroup$ Lol, you are clearly about as English as I am. Have this translated and you will laugh :) $\endgroup$ Oct 11, 2014 at 16:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .