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 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:


*

*Tree: $|V|-1=|E|$ 

*HandShake Theorem: $2|E|= \sum deg(v)$

*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.
 A: 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.
A: 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.
A: 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.$$
