0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ If you didn't need it to be connected, then you could have ten vertices all of degree one. But as you noted, a tree has to be connected (and cycle-free). So expect fewer vertices of degree one. $\endgroup$
    – hardmath
    Mar 17 at 5:39
  • $\begingroup$ As in fewer than 10? So my number should be somewhere <10? Sorry I just don't really get what to do. $\endgroup$
    – djmotto2
    Mar 17 at 5:42
  • $\begingroup$ The problem might be an exercise to reinforce some material just covered in your book or other course materials. The vertices of degree one in a tree are called leaves. Start with one vertex of degree three, and then add leaves at the ends of "branches". Repeat until you've used up your ten vertices. $\endgroup$
    – hardmath
    Mar 17 at 5:57
  • $\begingroup$ Try to solve smaller versions of the same problem? What's the maximum number of valence one vertices in a binary tree with $n=2, 3, \dots$ vertices? $\endgroup$ Mar 17 at 5:58
2
$\begingroup$

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.)

$\endgroup$
0
0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed explanation. I can see how to approach this problem and solve it now. $\endgroup$
    – djmotto2
    Mar 17 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.