A tree T has 2n vertices of degree 1, 3n vertices of degree 2 and n vertices of degree 3. find the number of vertices and edge in T

Question

it's tree problem

Answer 1

I just read a little about trees on Wikipedia, and I think this may be the answer...  ;-)

The total number of vertices will be 6n and it looks like the number of edges is 6n-1.

But can a tree be formed with this makeup of vertices-with-given-degrees for any n?

 

Well, as many vertices with degree 2 as we want can be put into a tree, because a degree 2 vertex can always be added in place of an existing edge, and likewise a vertex of degree 2 can be removed and replaced with an edge.  So the 3n degree-2 vertices will not be the problem.

 

What about the degree-3 and degree-1 vertices?  Since it has to be a single tree, no degree-1 vertex can be attached to another degree-1 vertex.  Likewise to not have any cycles in the tree, no degree-3 vertex can connect to itself, nor can the degree-3 vertices be in a loop. So with these constraints the degree-3 vertices are connected together in a kind of backbone and the remaining edges (like legs sticking out of a bug) will each have a degree-1 vertex on them.

 

So, is n=1 possible?  NO:

the single degree-3 vertex will have to have 3 degree-1 vertices attached, this is not 2*1.

 

n=2?  YES:

The two deg-3 vertices are connected by one edge and there will then be 4 'legs' sticking out, so that's 4 degree-1 vertices = 2*2 as desired.

 

n=3?  NO:

when the 3 deg-3 vertices are connected, there will be 5 'legs' sticking out, not the 2*3=6 that we'd want for 6 deg-1 vertices.

 

n=more? NO: (I think)

each time a deg-3 vertex is added the vertex number goes up 1 and the number of protruding legs goes up by 1:

deg-3  deg-1  <-- numbers of them

  4        6

  5        7

  6        8

  etc

and we'll never have the 1:2 ratio that we want.

 

So n=2

and vertices = 12, edges = 11.

One possible arrangement (there are many since the deg-2 vertices can be put anywhere) is:

 

                        1     1

  1---2---2---2---3----3---2---2---2---1

 

where the number is the degree of the vertex and the two "3"s each have an additional "1" attached above the line of vertices (I put them in but they may not align properly because of the font spacing.)

 

I hope this helps.