Let G be a k-connected graph and let S,T be disjoint vertex-sets of size at least k. Prove that G has k pairwise disjoint S,T paths.

Printable View

- Oct 27th 2010, 08:42 PMjzelltk-connected graph
Let G be a k-connected graph and let S,T be disjoint vertex-sets of size at least k. Prove that G has k pairwise disjoint S,T paths.

- Oct 30th 2010, 04:26 PMtom@ballooncalculus
Put a minimum vertex cut set in between the two blocks it will disconnect – call them S and T. Confirm that the size k of the cut set is reliably equal to the number of disjoint S, T paths. Then confirm that moving any vertex from it's own area into one of the other two, or outside them, can never alter the number of disjoint S,T paths, except where it reduces the size of S or T to less than k.