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