Why Does a Tree with n Vertices Have n − 1 Edges?

A tree is a finite, undirected, connected graph with no cycles. The statement is that if a tree has $n$ vertices, it has exactly $n-1$ edges. The key idea is to remove a vertex that is attached to the rest of the tree by just one edge, prove the claim for the smaller tree, and then put that edge back.

Proof by induction

We prove the claim for every positive integer $n$.

Base case: $n=1$. A tree with one vertex has no edges. Since $1-1=0$, the formula holds.

Inductive step. Assume that every tree with $n-1$ vertices has $n-2$ edges. Let $T$ be a tree with $n\geq 2$ vertices. We first show that $T$ has a leaf, a vertex of degree one.

Choose a simple path in $T$ that has as many edges as possible, and consider one of its endpoints, say $v$. The endpoint has a neighbor because the tree is connected and has more than one vertex. If it had a neighbor not on the path, that neighbor would extend the path, contradicting its maximal length. If it had an additional neighbor elsewhere on the path, the extra edge together with part of the path would form a cycle. Both possibilities are ruled out, so $v$ has exactly one neighbor: it is a leaf.

Delete $v$ and its one incident edge. The remaining graph is still connected: a path between any two remaining vertices cannot need to pass through a degree-one vertex as an intermediate vertex. It is also still acyclic, because deleting a vertex cannot create a cycle. Thus the remaining graph is a tree with $n-1$ vertices. By the inductive hypothesis, it has $n-2$ edges. Restoring $v$ and its one edge gives $T$ exactly

$$(n-2)+1=n-1$$

edges. This completes the induction.

Worked example

Consider a graph with vertices $A,B,C,D,E,F$ and edges

$$\{AB,\;BC,\;CD,\;CE,\;EF\}.$$

It is connected: every vertex can be reached from every other by following edges. It has no cycle, so it is a tree. There are $6$ vertices and $5$ edges, as the formula predicts: $6-1=5$.

You can also see the induction directly. Vertex $A$ is a leaf. Remove $A$ and the edge $AB$; the remaining tree has $5$ vertices and $4$ edges. Adding $A$ and $AB$ back increases the edge count by one, giving $5$ edges for the original tree.

Why the leaf argument works

Removing a leaf preserves both properties that define a tree. It preserves connectedness because the leaf cannot lie in the middle of a path between two other vertices: it has only one incident edge. It preserves acyclicity because removing part of a graph cannot introduce a cycle. These facts justify applying the induction hypothesis to the graph that remains.

The same reasoning also gives a useful way to construct a tree: start with one vertex and repeatedly add a new vertex using exactly one edge to the existing graph. Each added vertex contributes one edge, so after adding $n-1$ vertices there are $n-1$ edges. The leaf proof establishes that every finite tree can be reduced in the reverse way.

Common mistakes

• Using only that the graph is acyclic. A forest (an acyclic graph that may be disconnected) need not have $n-1$ edges. For example, two isolated vertices have $2$ vertices and $0$ edges. More generally, a forest with $k$ connected components has $n-k$ edges.
• Using only that the graph is connected. A connected graph can contain cycles and have more than $n-1$ edges. For example, a triangle has three vertices and three edges.
• Deleting an arbitrary vertex. An arbitrary vertex may have several incident edges. The proof needs a leaf, whose degree is exactly one, so the edge count changes by exactly one.
• Forgetting the base case. The one-vertex tree has zero edges, which is why the formula starts at $n=1$ and gives $1-1=0$.