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

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.