2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Marvelous solution!!! $\endgroup$ – Di Wang Nov 28 '17 at 16:06
  • $\begingroup$ @DiWang It wasn't that hard to come up with it. You had one inequality on $x$ and I tried to show that the RHS is greater or equal to $d$. This was equivalent to proving that $|V| \ge d+1$ $\endgroup$ – Stefan4024 Nov 28 '17 at 16:08
  • 1
    $\begingroup$ Exactly, $|V|≥d+1$ is the missing piece of the whole proof $\endgroup$ – Di Wang Nov 28 '17 at 16:17
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.