1

enter image description here

But I can find a counter example:

      *
    /   \
   *     *
  / \   / \
 *   * *   *

Here $k = 2$, but number of vertices is 6, and number of terminal vertices is 4.

qed
  • 1,083

1 Answers1

1

Actually $k=3$ here, since the top of the tree is an internal node. That correctly gives $2\cdot 3+1=7$ total vertices, and $k+1=4$ external vertices (the lowest endpoints in the picture).

coffeemath
  • 29,884
  • 2
  • 31
  • 52