Results 1 to 2 of 2

Thread: 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 $\displaystyle G$ is a k-edge-connected graph and $\displaystyle v,v_{1},v_{2},...,v_{k}$ are $\displaystyle k+1$ distinct vertices of $\displaystyle G $ then for $\displaystyle i = 1,2,...k $ there exist $\displaystyle v-v_{i} $ paths $\displaystyle P_{i} $ such that each path $\displaystyle P_{i} $ contains exactly one vertex of $\displaystyle {v,v_{1},v_{2},...,v_{k}}$, namely $\displaystyle v_{i}$, and for $\displaystyle i \neq j, P_{i} $ and $\displaystyle P_{j} $ are edge-disjoint
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,776
    Thanks
    2823
    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 $\displaystyle G$ is a k-edge-connected graph and $\displaystyle v,v_{1},v_{2},...,v_{k}$ are $\displaystyle k+1$ distinct vertices of $\displaystyle G $ then for $\displaystyle i = 1,2,...k $ there exist $\displaystyle v-v_{i} $ paths $\displaystyle P_{i} $ such that each path $\displaystyle P_{i} $ contains exactly one vertex of $\displaystyle {v,v_{1},v_{2},...,v_{k}}$, namely $\displaystyle v_{i}$, and for $\displaystyle i \neq j, P_{i} $ and $\displaystyle 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 $\displaystyle \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: Apr 15th 2010, 11:38 PM
  2. Graph problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 1st 2009, 12:48 PM
  3. Please help ! Graph problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Oct 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: Jul 4th 2007, 11:47 AM

Search Tags


/mathhelpforum @mathhelpforum