Results 1 to 2 of 2

Math Help - tree trouble

  1. #1
    Newbie
    Joined
    Sep 2006
    From
    Edmonton, AB
    Posts
    8

    Post tree trouble

    Let T be a tree with delta T being greater than or equal to k. Show that T has at least k end-vertices.

    Note that delta T is the greatest vertex degree.


    I believe that this can be solved using the Hand Shaking Lemma:

    Assume that T has k end vertices, and T is of order n, then:

    2e(T)= (sum of degs of verts of deg 1) + (sum of degs of verts of deg greater than 1)

    2e(T) = k(1) + (n-k)(
    this is where things stop.

    what i was hoping to do was to continue on in this manner until it reduced to e(T)= n-1 which is a condition of trees, and would therefore show that the assumption was correct. This is just not working out. Any thoughts?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2006
    From
    Edmonton, AB
    Posts
    8
    sorry, it should read
    2e(T) = k(1) + (n-k)(
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. tree
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 25th 2011, 07:56 AM
  2. tree diagram
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 8th 2010, 10:03 AM
  3. tree diagram help.
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 2nd 2010, 05:16 PM
  4. Decision tree
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: December 14th 2009, 03:05 AM
  5. Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 12th 2008, 03:17 AM

Search Tags


/mathhelpforum @mathhelpforum