Trees and Networks - Key Proof

The fundamental relationship between vertices and edges in trees is both elegant and essential for understanding tree structure.

DefinitionTree Edge-Vertex Relationship

Every tree with $n$ vertices has exactly $n-1$ edges.

Proof by Induction:

We prove by strong induction on $n$ .

Base case: For $n = 1$ , a tree with 1 vertex (isolated) has 0 edges. Indeed, $1 - 1 = 0$ . ✓

Inductive hypothesis: Assume every tree with $k < n$ vertices has exactly $k-1$ edges.

Inductive step: Let $T$ be a tree with $n$ vertices where $n \geq 2$ .

Since $T$ is connected and $n \geq 2$ , there exists at least one edge. Since $T$ is acyclic and connected, there exists a leaf vertex $v$ (a vertex of degree 1).

To see why a leaf exists: Since $T$ is connected with $n \geq 2$ , every vertex has degree $\geq 1$ . If all vertices had degree $\geq 2$ , we could construct an infinite simple path (start anywhere, always move to an unvisited neighbor, which exists by degree $\geq 2$ ). But $T$ is finite, so this is impossible. Thus some vertex has degree exactly 1 (a leaf).

Remove the leaf $v$ and its incident edge $e = \{v, u\}$ to get $T' = T - v - e$ .

Claim: $T'$ is a tree.

Connected: Any path in $T$ not using $v$ is still in $T'$ . Any path using $v$ must enter and exit via $u$ (since $v$ is a leaf), so we can route around $v$ .
Acyclic: Removing an edge can't create cycles.

By the inductive hypothesis, $T'$ has $(n-1)$ vertices and $(n-1) - 1 = n-2$ edges.

Therefore, $T$ has $n$ vertices and $(n-2) + 1 = n-1$ edges. ✓

This completes the induction. $\square$

Alternative Proof (Direct):

We can also prove this directly by showing:

Every connected graph with $n$ vertices has at least $n-1$ edges
Every acyclic graph with $n$ vertices has at most $n-1$ edges

Proof of (1): Build a spanning tree by BFS. Add edges one at a time, each connecting a new vertex. This requires at least $n-1$ edges.

Proof of (2): If a graph with $n$ vertices and $k$ connected components is acyclic, each component is a tree. Component $i$ with $n_i$ vertices has $n_i - 1$ edges. Total edges: $\sum(n_i - 1) = n - k \leq n - 1$ .

Since trees are both connected ( $k=1$ ) and acyclic, they have exactly $n-1$ edges. $\square$

ExampleConsequences

Adding any edge to a tree creates exactly one cycle
A connected graph with $n$ vertices and $n-1$ edges is a tree
A forest with $n$ vertices and $k$ components has $n-k$ edges
The complete graph $K_n$ has $\binom{n}{2} = \frac{n(n-1)}{2}$ edges, so an MST removes $\frac{n(n-1)}{2} - (n-1) = \frac{(n-1)(n-2)}{2}$ edges

Remark

This relationship makes trees maximally sparse connected graphs: removing any edge disconnects them, and adding any edge creates a cycle. The formula $|E| = |V| - 1$ provides a quick check for tree identification. In computational complexity, many tree algorithms achieve $O(n)$ time precisely because trees have linear edge count. The sparsity also makes trees amenable to dynamic programming: many optimization problems have recurrence relations on trees that exploit their recursive decomposition at any edge.