Proof that a tree on n vertices has n − 1 edges, by removing a leaf

Proof

We argue by induction on $n$.

1. A tree is connected, so it has at least one vertex. Thus $n \ge 1$.
2. Base case $n = 1$. An edge is a $2$-element set of vertices, and a $1$-element vertex set has no such subset. So $T$ has $0 = n - 1$ edges.
3. Induction step. Let $n \ge 2$, and assume that every tree with $n - 1$ vertices has $n - 2$ edges. Let $T$ have $n$ vertices.
4. By the leaf lemma, $T$ has a vertex $\ell$ of degree $1$. Let $\ell a$ be its only edge.
5. Let $T'$ be the graph $T$ with the vertex $\ell$ and the edge $\ell a$ removed. It has $n - 1$ vertices and one edge fewer than $T$.
6. $T'$ is acyclic: it is a subgraph of $T$, so each cycle of $T'$ is a cycle of $T$, and $T$ is acyclic.
7. $T'$ has a vertex, namely $a$. Let $x, y$ be vertices of $T'$.
8. Since $T$ is connected, it has a walk from $x$ to $y$. By every walk contains a path, $T$ has a path $(p_0, \dots, p_m)$ from $x$ to $y$.
9. The vertex $\ell$ is not $p_0 = x$ or $p_m = y$. If $\ell = p_i$ with $0 < i < m$, then $p_{i-1}$ and $p_{i+1}$ are two distinct neighbours of $\ell$, which contradicts $\deg(\ell) = 1$.
10. So the path avoids $\ell$, and hence also the edge $\ell a$. It is a walk in $T'$ from $x$ to $y$. Thus $T'$ is connected.
11. By steps 6 and 10, $T'$ is a tree with $n - 1$ vertices. By the induction hypothesis it has $n - 2$ edges.
12. By step 5, $T$ has $(n - 2) + 1 = n - 1$ edges. This completes the induction.