Results 1 to 4 of 4

Math Help - Path Length

  1. #1
    Len
    Len is offline
    Member
    Joined
    Mar 2008
    Posts
    93
    Thanks
    1

    Path Length

    Prove that if G is a simple graph with minimum degree k, where k \geq 2 then G has a path of length at least k.

    I've been bouncing through ideas all day but I keep finding flaws in them. I feel like I must show that G is hamiltonian but I do not know how to do that.

    Any help is appreciated, plus rep like always.

    Thanks
    Last edited by Len; February 10th 2011 at 11:42 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let x_1,...,x_r be the longest simple path in the graph, and suppose (we want to get a contradiction) that r < k.

    What happens with the neighbours of x_r ? Do they all appear in the path ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Len
    Len is offline
    Member
    Joined
    Mar 2008
    Posts
    93
    Thanks
    1
    Quote Originally Posted by PaulRS View Post
    Let x_1,...,x_r be the longest simple path in the graph, and suppose (we want to get a contradiction) that r < k.

    What happens with the neighbours of x_r ? Do they all appear in the path ?
    Thanks for the reply.

    So x_r would have to be connected to at least k points(min degree). Since r \geq k+1 because r is connected to k points and then we add the r point itself. Therefore r > k which is a contradiction of r < k and hence G has a path length of at least k.

    This makes more sense, if I'm wrong please correct me but thanks again!

    PS PaulRS as in the creator of RS? :P
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Len View Post
    Thanks for the reply.

    So x_r would have to be connected to at least k points(min degree). Since r \geq k+1 because r is connected to k points and then we add the r point itself. Therefore r > k which is a contradiction of r < k and hence G has a path length of at least k.

    This makes more sense, if I'm wrong please correct me but thanks again!

    PS PaulRS as in the creator of RS? :P
    ( first I should have written r\leq k and not r<k )

    Well, if the path had length k-1 or less, then there'd be at most k nodes in the path but then x_r has a neighbour that is none of the others in the path, thus we would be able to extend the path (adding the new node at the end) contradicting the maximality of the length of the path.

    PS: No, it's my initials.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Finding length of path over an interval
    Posted in the Calculus Forum
    Replies: 5
    Last Post: October 17th 2010, 09:44 PM
  2. Finding path length of curve
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 21st 2009, 03:06 AM
  3. Length needed from a known length and angle
    Posted in the Geometry Forum
    Replies: 4
    Last Post: July 21st 2009, 07:17 AM
  4. degree of a path, path homotopy.
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 19th 2009, 06:37 PM
  5. arc length and parameterized curve length
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 5th 2008, 03:33 AM

Search Tags


/mathhelpforum @mathhelpforum