SOLUTION: A binary tree is a connected graph with no cycles, where each vertex has a degree less than or equal to 3. What is the maximum number of vertices of degree one that a binary tree w

Algebra.Com
Question 1176930: A binary tree is a connected graph with no cycles, where each vertex has a degree less than or equal to 3. What is the maximum number of vertices of degree one that a binary tree with 15 vertices can have?
Answer by greenestamps(13200)   (Show Source): You can put this solution on YOUR website!


The degree of each vertex is either 1 or 2.

A total of 15 vertices with a maximum number of vertices of degree 1 means a minimum number of vertices of degree 2.

The total of 15 vertices will be reached fastest if the vertices in the first few levels of the tree all have degree 2.

Instead of trying to draw binary trees in typed text, I'll make a chart of the numbers of vertices of degree 1 or 2, and the total numbers of vertices, for increasing numbers of levels.
   # of   vertices of  vertices of   total
  levels   degree 2     degree 1    vertices
 --------------------------------------------
     1        0            1           1
     2        1            2           3
     3        3            4           7
     4        7            8          15

So the maximum number of vertices of degree 1 in a binary tree with 15 vertices is 8.


RELATED QUESTIONS

A binary tree is a connected graph with no cycles, where each vertex has a degree less... (answered by CPhill)
If a tree is connected graph with no cycles then how many non isomorphic trees with 5... (answered by ikleyn)
Can anyone tell me if I'm on the right track with this: Question: Let G = (V, E) be a (answered by richard1234)
Given tan theta= -9/4, where 270 degrees is less or equal than theta and less or equal... (answered by Alan3354)
Solve the system of inequalities by graphing. y>x 2x+y (answered by checkley71)
a. find the value of the objective function at each corner of the graphed region. b.... (answered by KMST)
please help! 2/3(x+9) is less than or equal to 1/3(2x+12) A. X is less than or... (answered by Earlsdon)
An Eulerian Path is a graph traversal that starts at some vertex and traverses every edge (answered by CPhill)
Can somone please tell me how to do this i am so confused. Let X be a random variable... (answered by stanbon)