tree has exactly $k$ nodes with degree $4$. Show that this tree has $2k+2$ leaves.

Question

Prove:

If a tree has exactly $k \geq 1 $ nodes with degree $4$, then this tree has at least $2k +2 $ leaves. ( nodes with degree $< 4 $ are only allowed for the leaves ).

So I think that we can solve this with induction.

$ k = 1$ :

So we have exactly one node with degree $4$. this node has to have at least $4$ leaves, because of the degree. Or am I wrong?

$ k \rightarrow k+1$:

We have a tree with $k$ nodes with degree $4$. We know that we have at least $2k+2$ leaves. We replace one of the leaves with a node and build a node of degree $4$. So we "lost" a leave but "gain" 3 new leaves. So we conclude that we have a tree with $k+1$ nodes with degree $4$ and $2k+2-1+3 = 2k+4 =2(k+1) +2 $ leaves. Am I right?

Answer 1

Your proof could be made to work but there is still more you need to do for it to be considered a proof.

The one detail you need to observe is that you can construct any tree w $k+1$ degree-4 nodes from one with $k$ nodes as you did. What if all nodes adjacent to a leaf have degree 5 or greater? A way around this is to conclude that a tree with $k''$ nodes of degree at least 4 has at least $2k''+2$ leaves.

---

An alternate proof: Let $F$ be a forest where every nonleaf vertex has degree at least 4. Let $n$ be the number of vertices in $F$. The number of edges that $F$ can have is at most $n-1$ with equality reached iff $F$ is a tree and not a forest with two or more connected components. [make sure you see why]

Let $k$ be the number of vertices of degree 4 and $k'$ the number of vertices of degree 5 or greater.

Letting $l$ be the number of leaves, then $n=l+k+k'$. So the number of edges that $F$ can have is at most $n-1 =$ $l+k+k'-1$.

The number of edges $F$ has however at least $\frac{1}{2} (5k'+4k+l)$ [this is $\frac{1}{2}$ times a lower bound on the sum of the degrees of the vertices of $F$, make sure you see why that is the number of edges in $F$]

Thus $2(l+k+k')-2 \ge 5k'+4k+l$ $\implies$ $l \ge 3k'+2k+2$.

*****If every interior vertex has degree 4 and the graph is a tree then this inequality is tight. Can you trace through the proof to see why?

*****You could trace through this proof to conclude: $l=\sum_{d \geq 2} (k_d-2)+2$, where $k_d$ is the number of vertices of degree $d$ $(d=2,3,\ldots$) if the graph is a tree, and $l=\sum_{d \geq 2} (k_d-2)+1+c$, if the graph is a forest with $c$ distinct connected components. From this the lower bound of $l \geq 2k_4+2$ for $l$, which is what you wanted to derive, is an immediate consequence.

Answer 2

I do not see why it is important to include the condition that only vertices of degree less than $4$ are leaves. I am going to prove a general statement. Note that this proof can be rewritten so that it is an inductive proof

Proposition. Let $k\geq 1$ and $d\geq 2$ be integers. Let $T$ be a (finite) tree with exactly $k$ vertices of degree $d$. Then, $T$ has at least $(d-2)k+2$ leaves.

Suppose on the contrary that, for some positive integer $k$, there exists a tree with exactly $k$ vertices of degree $d$ but with fewer than $(d-2)k+2$ leaves. Take $T$ to be such a tree with the smallest possible $k$. If $k>1$, then let $u$ be a vertex of $T$ with degree $d$. Suppose that $v_1,v_2,\ldots,v_d$ are the neighbors of $u$. Let $C_i$ be the connected component of $T-u$ containing $v_i$, for $i=1,2,\ldots,d$. Take $T_i$ to be the tree with vertices from $C_i$ and an extra vertex $u_i$, which is a leaf and adjacent to $v_i$.

For a graph $G$, let $n_t(G)$ denote the number of vertices of degree $t\in\mathbb{Z}_{\geq 0}$ in $G$. Clearly, we have $$\sum_{i=1}^d\,n_1(T_i)=n_1(T)+d<\big((d-2)k+2\big)+d\,.$$ Since $T$ is a tree with the smallest $k=n_d(T)$ that violates the claim, we must have $$n_1(T_i)\geq (d-2)\,n_d(T_i)+2$$ for all $i=1,2,\ldots,d$. This shows that $$\begin{align}\big((d-2)k+2\big)+d&>\sum_{i=1}^d\,n_1(T_i)\geq \sum_{i=1}^d\,\big((d-2)\,n_d(T_i)+2\big) \\&=(d-2)\,\sum_{i=1}^d\,n_d(T_i)+2d=(d-2)\,(k-1)+2d\\&=\big((d-2)k+2\big)+d\,.\end{align}$$ This is absurd, so the assumption that $k>1$ cannot be true. Hence, $k=1$.

However, it is easy to show that every tree with exactly $1$ vertex of degree $d$ as at least $d$ leaves. Thus, $k=1$ cannot hold either, and the proposition must be true. (Note that the minimum number of leaves $(d-2)k+2$ is achieved if and only if $T$ has only vertices of degree $1$ or $d$. In such cases, $T$ has $(d-1)k+2$ vertices and $(d-1)k+1$ edges.)

Corollary. For integers $d_1,d_2,\ldots,d_m$ with $1<d_1<d_2<\ldots<d_m$, we have $$n_1(T)\geq \sum_{i=1}^m\,(d_i-2)\,n_{d_i}(T)+2$$ for every tree $T$ with at least two vertices.

As before, $n_t(G)$ denote the number of vertices of degree $t\in\mathbb{Z}_{\geq 0}$ in a finite graph $G$. In the corollary, the equality holds iff $n_t(T)=0$ for every integer $t\geq 2$ such that $t\notin \{d_1,d_2,\ldots,d_m\}$. In this case, $T$ has exactly $\displaystyle\sum_{i=1}^m\,(d_i-1)\,n_{d_i}(T)+2$ vertices and $\displaystyle\sum_{i=1}^m\,(d_i-1)\,n_{d_i}(T)+1$ edges.