Results 1 to 2 of 2

Math Help - k-connected graph

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    k-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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,034
    Thanks
    49
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Every connected graph contains a maximal tree
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 4th 2011, 06:44 AM
  2. Replies: 4
    Last Post: April 28th 2011, 01:32 AM
  3. Edge connected graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 4th 2010, 10:08 AM
  4. How many connected components does this graph contain?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2009, 01:09 PM
  5. Replies: 1
    Last Post: April 18th 2008, 07:19 AM

Search Tags


/mathhelpforum @mathhelpforum