A graph G of order n 2k is hconnected if and only if for ev

A graph G of order n > 2k is h-connected if and only if for every two disjoint sets V_1 and V_2 of k distinct vertices each, there exist k pairwise disjoint paths connecting V_1 and V_2.

Solution

G is k-connected. Let V1 and V2 be disjoint vertex sets of size k. Create G by adding a vertex v1 and all edges between v1 and V1 and a vertex v2 and all edges between v2 and V2. Now use the expansion lemma to see that G is k-connected.

Assume G has a vertex cut SS of size less than k. Let V be the smallest component of GS

Make a vertex set V1 by taking k vertices from V if possible, fill up with vertices of S if necessary.

Make a vertex set V2 by taking kk vertices from the other components of GS if possible, fill up with unused vertices from S if necessary.