Thread: [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

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.