1
$\begingroup$

I'm trying to prove the following, but I am not sure if my approach can be accepted as a mathematical proof.

Let $T$ be a tree with $n \ge 2$ nodes. Prove that the number of pendant nodes (nodes with $d(v) = 1$) equals:

$$2 + \sum_{v:d(v)\ge3} (d(v) - 2)$$

With $n = 2$ there are 2 pendant nodes, with $n = 3$ there are 2 pendant nodes and one node with $d(v) = 2$. Adding just an edge would create a cycle, so for every new edge you need to connect it to an existing node.
When adding a node you have two options:

  • Add it to a pendant node, removing the existing pendant and increasing their degree to 2 but adding a new pendant node.
  • Adding it to a node with $d(v) \ge 2$, increasing their degree by one and adding one pendant node.

This results in the 2 initial pendants plus one extra pendant for each node added to a node with $d(v) \ge 2$.

$\endgroup$
  • $\begingroup$ Yes, I would accept this as a valid proof. $\endgroup$ – saulspatz Mar 5 at 17:19
  • 1
    $\begingroup$ The main problem with the argument is that you need to show that every tree can be obtained by adding nodes. While this is true, the argument is simpler if you show/use that it is always possible to remove a (leaf) node from an $n$ node tree to obtain a $n-1$ node tree, and then use induction on $n$. $\endgroup$ – Hagen von Eitzen Mar 5 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.