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

Question

Full question as the title was a maximum of 150 characters. 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 10 vertices can have?

I am really struggling to understand this question and have not seen questions that are similar. I was hoping someone could push me into the right direction. As I understand the problem, we can only use 10 vertices. So would the maximum amount of vertices not be 10? I tried drawing it out and don't see how it can be any larger.

Answer 1

Let $v_1$ be the number of vertices of degree $1$, $v_2$ the number of vertices with degree $2$, and $v_3$ the number of vertices with degree $3$, so that

$$v_1+v_2+v_3=10\,.\tag{1}$$

I’m going to assume that you already know that if a tree has $v$ vertices, it has $v-1$ edges, and I’m going to assume that you know the handshaking lemma. If you put those two facts together, you find that

$$v_1+2v_2+3v_3=2\cdot(10-1)=18\,.\tag{2}$$

Subtract $(1)$ from $(2)$ to find that

$$v_2+2v_3=8\,.\tag{3}$$

You want to make $v_1$ as large as possible, so $(1)$ tells you that you want to make $v_2+v_3$ as small as possible. Experiment with possible values of $v_2$ in $(3)$ to find which one minimizes $v_2+v_3$, and use $(1)$ to find the maximum possible value of $v_1$. (When you’ve done all that, it would be a good idea actually to find a tree with $10$ vertices and the maximum possible number of leaves.)

Answer 2

For a binary tree (each node has at most two children) with $n$ vertices,

• Let $f(n)$ be the maximum possible number of vertices of degree $1$.
• Let $g(n)$ be the maximum possible number of leaves.$\\[4pt]$

Our goal is to compute $f(10)$.

The values of $f$ can be expressed in terms of the values of $g$ by $$ f(n)= \begin{cases} 0&\qquad\;\;\,\text{if}\;\,n\le 1\\[4pt] \max\,\bigl\{g(n),1+g(n-1)\bigr\}&\qquad\;\;\,\text{if}\;\,n > 1\\[4pt] \end{cases} $$ and $g$ can be computed recursively by $$ \;\;\;\;\;\, g(n)= \begin{cases} 0&\;\text{if}\;\,n=0\\[4pt] 1&\;\text{if}\;\,n=1\\[4pt] \max\,\bigl\{g(a)+g(b){\,{\large{\mid}}\,}(a,b)\in X_n\bigr\}&\;\text{if}\;\,n > 1\;\;\;\;\;\\[4pt] \end{cases} $$ where for $n > 1$, we define $X_n$ as the set of all pairs $(a,b)$ of integers such that $0\le a\le b$ and $a+b=n-1$.

Computing some early values of $g$, it becomes evident that $$ g(n)=\left\lceil\frac{n}{2}\right\rceil \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\;\;\;\; $$ for all $n$, which can be proved by strong induction on $n$.

It follows that for all $n > 1$ we have $$ f(n)=\left\lceil\frac{n+1}{2}\right\rceil \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\, $$ In particular we have $f(10)=6$.