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 ->
Functions
-> 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
Log On
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):
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.
