Results 1 to 2 of 2

Math Help - [SOLVED] Graph Theory - Trees

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    35

    [SOLVED] Graph Theory - Trees

    Hi,

    I'm working on a problem and I'm having troubles undestanding the solution. The question is as follows:

    Let T be a tree having one vertex of degree i for each i = 2,....,k and an undisclosed number of end-vertices. Find |T|.

    The solution starts off as:
    If n = |T| then observing T has k-1 vertices > 1...

    I can't get why T would have k-1 vertices > 1...Please help!!!

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    If T is a tree having one vertex of degree i for each i = 2,...,k, then you can get then next one by taking one of the end-vertices and adding k new edges to k new end-vertices.

    Here's an illustration for k=2,3 and 4. Each time, you take the vertex at the right-hand end of the diagram and add new edges to it to get the next diagram.
    Code:
    o——o——o
    
    Add two new edges to get:
    
    o——o——o——o
          |
          o
    
    Add three new edges to get:
    
             o
             |
    o——o——o——o——o  
          |  |
          o  o
    
    Now add four new edges to the rightmost vertex...
    There is only one vertex of degree i for each i>1, hence k-1 such vertices as k goes from 2 to k.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 2nd 2011, 05:39 AM
  2. Graph Theory - Trees and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 9th 2010, 11:14 PM
  3. Graph Theory question about trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2009, 02:52 AM
  4. [SOLVED] Graph Theory and Labeled Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2009, 07:10 AM
  5. Graph theory: Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 3rd 2009, 12:30 PM

Search Tags


/mathhelpforum @mathhelpforum