3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$
    – Mike
    Nov 14 '18 at 1:29
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Nov 13 '18 at 21:16
  • $\begingroup$ @Batominovski in general yes but the assumption by the OP is that only leaves have degree $<4$ $\endgroup$
    – Mike
    Nov 13 '18 at 21:18
  • $\begingroup$ What about vertices of degree more than $4$? There is no restriction on that. $\endgroup$ Nov 13 '18 at 21:19
  • $\begingroup$ @Batominovski fixed it to allow for that possibility $\endgroup$
    – Mike
    Nov 13 '18 at 21:23
  • $\begingroup$ For whatever reason I had read that every interior vertex has degree 4 $\endgroup$
    – Mike
    Nov 13 '18 at 21:23

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.