Results 1 to 2 of 2

Math Help - Graph problem

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    Glasgow
    Posts
    1

    Graph problem

    I have big problem to solve, could someone help

    Prove or disprove: If G is a k-edge-connected graph and v,v_{1},v_{2},...,v_{k} are k+1 distinct vertices of  G then for  i = 1,2,...k there exist v-v_{i} paths  P_{i} such that each path  P_{i} contains exactly one vertex of {v,v_{1},v_{2},...,v_{k}}, namely v_{i}, and for  i \neq j, P_{i} and  P_{j} are edge-disjoint
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,658
    Thanks
    1615
    Awards
    1

    Re: Graph problem

    Quote Originally Posted by Franek222 View Post
    I have big problem to solve, could someone help
    Prove or disprove: If G is a k-edge-connected graph and v,v_{1},v_{2},...,v_{k} are k+1 distinct vertices of  G then for  i = 1,2,...k there exist v-v_{i} paths  P_{i} such that each path  P_{i} contains exactly one vertex of {v,v_{1},v_{2},...,v_{k}}, namely v_{i}, and for  i \neq j, P_{i} and  P_{j} are edge-disjoint
    I find this description hard to follow.
    However, you may find this webpage useful.

    Note that the degree of any vertex is \ge k. That gives some bound on the number of edges.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. graph problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 15th 2010, 11:38 PM
  2. Graph problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2009, 12:48 PM
  3. Please help ! Graph problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 18th 2008, 07:11 AM
  4. Graph-problem (TI-84 Plus). Need help!
    Posted in the Calculators Forum
    Replies: 2
    Last Post: May 13th 2008, 04:14 AM
  5. Graph Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 4th 2007, 11:47 AM

Search Tags


/mathhelpforum @mathhelpforum