Prove If G is a kconnected graph and u v1 v2vk are k1 distin

Prove: If G is a k-connected graph and u, v1, v2,....vk are k+1 distinct vertices of G, then there exist internally disjoint u-vi paths (1 <= i <= k) in G

Solution

Proof: Construct a new graph H from G by adding a new vertex v together with the edges vv_{i ,} i = 1,2,...,k.

Since G is k-connected, H is k-connected.

By theorem (Whitney\'s characterization ) : A graph G of order n > 1 is k-(vertex)connected (1 less equal k less equal n–1) iff for each pair u,v of distinct vertices there are at least k internally disjoint v-u paths in G.

The restriction of these paths to G yields the desired internally disjoint u-v_i paths.

===============

(Latex editor was not working so i wrote less equal instead of symbol.)

WE have : there exist k internally disjoint u–v paths in H