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

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?

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

• Yes indeed, if you know the number $n_d$ of nodes of degree $d$ for each $d \geq 3$ and the number $c$ of components in the forest, you can calculate exactly the number of leaves which is $1+c+\sum_{d \geq 3} n_d(d-2)$. A lower bound of $2n_4+2$ for a tree, which the OP was asked to establish, is an easy consequence from this formula. Good answer!
– Mike
Nov 14 '18 at 1:29

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.

• I don't think your proof is correct. A tree with $k$ vertices of degree $4$ may have vertices of degree $3$ for example. So, $n=l+k$ is not correct. Also, $F$ does not necessarily have $\dfrac{4k+l}{2}$ edges. Nov 13 '18 at 21:16
• @Batominovski in general yes but the assumption by the OP is that only leaves have degree $<4$
– Mike
Nov 13 '18 at 21:18
• What about vertices of degree more than $4$? There is no restriction on that. Nov 13 '18 at 21:19
• @Batominovski fixed it to allow for that possibility
– Mike
Nov 13 '18 at 21:23
• For whatever reason I had read that every interior vertex has degree 4
– Mike
Nov 13 '18 at 21:23