Trees

A path is a sequence of vertices joined by edges. A graph is connected if there is a path between every two vertices. A tree is a connected graph with no cycles.

We use one fact: every tree with at least $2$ vertices has a leaf, a vertex of degree $1$.

1. 01Base case: a tree with $1$ vertex has $0$ edges, which is $1 - 1$.Base case
2. 02Assume every tree with $k$ vertices has $k - 1$ edges. Take a tree with $k + 1 \ge 2$ vertices.Inductive hypothesis
3. 03It has a leaf. Remove the leaf and its one edge. What remains is a tree with $k$ vertices.Leaf removal
4. 04By the hypothesis, it has $k - 1$ edges, so the original had $k = (k + 1) - 1$ edges. $\blacksquare$Add the edge back