Number of Edges in a Forest

Theorem

Let $F = \left({V, E}\right)$ be a forest with $n$ nodes and $m$ components.

Then $F$ contains $n-m$ edges.

Proof

By definition, a forest is a disconnected graph whose components are all trees.

Let the number of nodes in each component of $F$ be $n_1, n_2, \ldots, n_m$ where of course $\displaystyle \sum_{i=1}^m n_i = n$.

From Number of Edges in Tree, the number of edges in tree $i$ is $n_i - 1$.

So the total number of edges in $F$ is:

$\displaystyle \sum_{i=1}^m \left({n_i - 1}\right) = \sum_{i=1}^m n_i - \sum_{i=1}^m 1 = n - m$

$\blacksquare$

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 4.1$: Problem $7$