A tree $T$ has least 3 vertices, the degree of a non-pendant vertex $\ge d$, prove that there are at least d number of pendant vertices in T

Question

Let G be a tree on at least 3 vertices in which all non-pendant vertices have degree d or greater. Prove that the number of pendant vertices in G is at least d.

This is my try:

1. Tree: $|V|-1=|E|$
2. HandShake Theorem: $2|E|= \sum deg(v)$
3. Let $x$ be the number of pendant vertices (degree 1), There are $|V|-x$ ( degree >= d) non-pendant vertices. So $\sum deg(v) \ge x+(|V|-x)d$

Therefore:

• $2|E|= \sum deg(v)$

• $2(|V|-1)= \sum deg(v) \ge x+(|V|-x)d$

• $2|V|-2 \ge x+|V|d-xd$

• $ x\ge \frac{(d-2)|V|+2}{d-1}$ (where |V|>=3)

and I am getting nowhere.

Answer 1

Continuing from what you have we need to prove that $\frac{(d-2)|V|+2}{d-1} \ge d$. First note that $|V| \ge d+1$. This is true as a non-pendant vertext has to be connected to $d$ other distinct vertices (no cycles in tree). "+1" comes from the non-pendant vertex. Therefore:

$$x \ge \frac{(d-2)|V|+2}{d-1} \ge \frac{(d-2)(d+1)+2}{d-1} = \frac{d^2-d - 2 + 2}{d-1} = d$$

Hence the proof.

Answer 2

Lemma: There is a non-pendant vertex, which is incident to at most one other non-pendant vertex.

Proof: Delete all the pendant vertices; the result is still a tree (of all the previously non-pendant vertices), which must have at least one pendant vertex.

Now we proceed by induction on the number of non-pendant vertices. Base case: one non-pendant vertex, with $d$ incident pendant vertices. Inductive case: select a non-pendant vertex incident to at most one other non-pendant vertex, using lemma. It has degree at least $d$, so at least $d-1$ incident pendant vertices. Strip away all of its pendant vertices, which turns it into a pendant vertex itself. The resulting tree has one fewer non-pendant vertices, so has at least d pendant vertices by the inductive hypothesis. Hence, going back to the original tree, we have at least $d-1+(d-1) \ge d $ pendant vertices.

Answer 3

By definition of a non-pendant vertex, $d\geq 2$. Then I will proceed just as you did but change the notations a bit. Suppose $p$ and $q$ are the number of pendant and non-pendant vertices so that $|V|=p+q$. Then $$2(p+q-1)\geq p+qd\Longrightarrow p\geq qd-2(q-1).$$ But $d\geq 2$ so $$p\geq qd-d(q-1)=d.$$