Results 1 to 2 of 2

Math Help - graph theory proof

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    32

    graph theory proof

    prove that in a simple connected graph if every vertex has a degree at least m, then there is a path of length at least m

    any hints? i made a path: v0 with deg=1, v1 with deg=2,...vm with deg=m. then said this path has a length of at least m and a degree of at least m.
    i'm not sure if that is right?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by mathh18 View Post
    prove that in a simple connected graph if every vertex has a degree at least m, then there is a path of length at least m

    any hints? i made a path: v0 with deg=1, v1 with deg=2,...vm with deg=m. then said this path has a length of at least m and a degree of at least m.
    i'm not sure if that is right?
    The basic idea is to construct the path inductively. In each step you can find a new vertex, which is not a neighbor of the vertices you've already used.

    More in detail:
    First, notice that the whole graph has at least m+1 vertices. (Do you know why?)

    Start with any vertex v1. Choose any neighbor of it for v2.
    If m=1 you're done.
    If m>1 than v2 has a neighbor different from v1. (Otherwise the degree of v2 would be 1.) Choose any such neighbor for v3.

    If you already have v1,v2,...,vk for some k<=m then:
    Choose for v_{k+1} any of neighbors of vk different from v1,v2,...,v_{k-1}. Again such a vertex must exist, otherwise the degree of vk would be at most k-1, which is less than m.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 12:16 AM
  2. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 20th 2010, 02:27 AM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2010, 11:00 PM
  4. Graph theory: proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 29th 2009, 12:00 PM
  5. Graph Theory Proof please:-
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2008, 03:06 PM

Search Tags


/mathhelpforum @mathhelpforum