A binary tree is a connected graph with no cycles, where each vertex has a degree less than or equal to 3.

Question

What is the maximum number of vertices of degree one that a binary tree with 15 vertices can have?

Answer 1

What is probably implied here is a straight line of 15 vertices connected to each other by 1 edge:

o---o---o ....... o---o

1 2 3 ........14 15

However, the question is flawed in some way. First of all what is described is a k-ary tree, where k<=3, since bi-nary means k=2 only. Second, the graph is already said to have 15 vertices (max-min is the same 15), therefore no matter how you connect them there will be 15 vertices and 14 edges. What changes is the depth of the tree, min depth = 3 and max depth = 14.