# Thread: [SOLVED] Graph Theory - Trees

1. ## [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...

Thanks

2. 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.