Trees are the leanest connected graphs: family trees, file folders, the branches of a decision. Using paths and connectedness, they have several equivalent definitions, and one tidy count.
Key idea
A tree is a connected graph with no cycles. For a graph with $n$ vertices these are equivalent: it is a tree; there is exactly one path between any two vertices; it is connected with $n - 1$ edges; it has no cycles and $n - 1$ edges. Every tree with at least $2$ vertices has at least $2$ leaves (vertices of degree $1$).
Why it works
Why $n - 1$ edges? Take a longest path in the tree; its end has degree $1$, because any other edge there would either extend the path or close a cycle. So every tree has a leaf. Remove a leaf and its edge: what remains is still connected with no cycles, a tree with one vertex fewer and one edge fewer. Repeat until one vertex and $0$ edges remain. Each step removed one vertex and one edge, so the original had exactly one edge fewer than vertices. Adding any edge to a tree joins two vertices that already had a path between them, so it creates exactly one cycle.
Worked examples
Worked example: Counting edges
A tree has $25$ vertices. How many edges? A forest (a graph with no cycles) has $25$ vertices and $4$ components. How many edges?
- Tree: $25 - 1 = 24$ edges.
- Forest: each component is a tree with one edge fewer than vertices; over $4$ trees that is $25 - 4 = 21$ edges.
Answer: $24$ and $21$
Worked example: Counting leaves
A tree has $3$ vertices of degree $3$, $1$ vertex of degree $4$, and every other vertex is a leaf. How many leaves?
- Let $\ell$ be the number of leaves. Then $v = 4 + \ell$ and $e = v - 1 = 3 + \ell$.
- Handshake: $3 \cdot 3 + 4 + \ell = 2(3 + \ell)$, so $13 + \ell = 6 + 2\ell$ and $\ell = 7$.
- Shortcut: $\ell = 2 + \sum (d - 2)$ over the vertices with $d \ge 3$: $2 + 1 + 1 + 1 + 2 = 7$.
Answer: $7$
Common mistake
Calling any graph with $n - 1$ edges a tree. A triangle plus one separate vertex has $4$ vertices and $3$ edges, yet it has a cycle and is not connected. The edge count is a test only together with "connected" or "no cycles." Check both conditions, or use one of them plus the count.