Prove that each tree $T=(V,E)$ with $|V| \geq 2$ contains at least $2$ leaves.

54 Views Asked by At

I'm not sure if this lemma has a name or not but here goes:

Every tree $T=(V,E)$ with $|V| \geq 2$ contains at least $2$ leaves.

The proof for this relies on the fact that if we start with only $2$ nodes, $v_1,v_2 \in V$, then we have an $e \in E$, which connects $v_1$ and $v_2$, then $T$ has $2$ leaves. If we have more than $2$ nodes, then we can pick either $v_1$ or $v_2$ and go in either direction. If we go in the direction of $v_1$ and it is not an end node, then we go to the succeeding node. If that is an end node, then we have one leaf. However, since we didn't move in the direction of $v_2$, we have a total of $2$ leaves. We can repeat this for any number of nodes on either side.

However, how can we argue that it's possible for there to be more than $2$ leaves?