The Edge Count Formula for Forests

Why Count Edges Component by Component?

A forest may consist of several separate pieces, and some of those pieces may be isolated vertices with no incident edges. Counting each connected component separately keeps these cases visible. The central fact is that a tree on $k$ vertices has $k-1$ edges; adding this count over the components gives the edge count for the whole forest.

All graphs in this tutorial are finite and simple: they have no loops or multiple edges. A walk is a sequence of vertices in which consecutive vertices are adjacent. A path is a walk whose vertices are distinct. A cycle is a sequence $v_0,v_1,\ldots,v_{k-1},v_0$, where $k\ge3$, the vertices $v_0,\ldots,v_{k-1}$ are distinct, and each consecutive pair is adjacent, including $v_{k-1}v_0$. Thus a cycle is closed, while a path has distinct vertices and is not closed.

Definition: A graph is connected if every pair of its vertices can be joined by a path. Its connected components are its maximal connected subgraphs. A tree is a connected graph with no cycles. A forest is a graph with no cycles; it need not be connected. We allow the graph with no vertices: it has no components.

A component containing just one vertex is a tree and has no edges. It is an isolated vertex in the full graph if it has no incident edges. In particular, isolated vertices count as components and must be included when counting $c$.

The Edge Count for One Tree

Lemma: If a tree $T$ has $k$ vertices, then it has $k-1$ edges.

Proof. We use induction on $k$. If $k=1$, simplicity rules out loops, so $T$ has zero edges, which is $1-1$. Now let $k\ge2$, and assume the claim holds for every tree with fewer than $k$ vertices. Choose a longest path in $T$; one exists because $T$ is finite. An endpoint $x$ of this path has degree one. Indeed, it has at least its path-neighbor. If it had a neighbor outside the path, that neighbor could be appended to give a longer path. If it had another neighbor on the path, the segment of the path between that neighbor and $x$, together with the extra edge, would form a cycle. Both possibilities contradict the choice of path or the fact that $T$ has no cycles.

Delete $x$ and its one incident edge, and call the resulting graph $T'$. It is acyclic because deleting vertices and edges cannot create a cycle. It is connected: for any two remaining vertices, a path between them in $T$ cannot use $x$ as an internal vertex, since $x$ has only one incident edge. Therefore that path remains in $T'$. So $T'$ is a tree on $k-1$ vertices. By induction it has $(k-1)-1=k-2$ edges. Restoring $x$ restores exactly one edge, so $T$ has $(k-2)+1=k-1$ edges. This proves the claim for every $k\ge1$. $\square$

The induction step relies on removing a vertex of degree one, not merely any vertex. Removing a vertex of higher degree could delete several edges, so the edge count would not follow from the same calculation.

The Forest Edge Count Formula

Theorem: If a finite forest $G$ has $n=|V(G)|$ vertices and $c$ connected components, then $$ |E(G)|=n-c. $$ This includes the empty graph, for which $n=c=0$.

Proof. Let the components of $G$ be $T_1,\ldots,T_c$, and let $k_i$ be the number of vertices in $T_i$. Each component is connected by definition, and it is acyclic because it is a subgraph of the forest. Hence each $T_i$ is a tree. The components partition the vertex set, so $\sum_{i=1}^{c} k_i=n$, and their edge sets partition the edge set. By the lemma, component $T_i$ has $k_i-1$ edges. Therefore $$ |E(G)|=\sum_{i=1}^{c}(k_i-1) =\sum_{i=1}^{c}k_i-c =n-c. $$ If $G$ is empty, then $c=0$ and both sums have no terms; their value is zero, so the same equality gives $|E(G)|=0-0=0$. $\square$

This proof also explains the subtraction by $c$: each component contributes one fewer edge than vertices, including a one-vertex component, which contributes $1-1=0$ edges. The count does not depend on the shapes of the components.

Worked Example: Two Tree Components and an Isolated Vertex

Let $G=(V,E)$, where $V=\{a,b,c,d,e,f,g\}$ and $E=\{ab,bc,cd,ef\}$. The vertices $a,b,c,d$ form one component, $e,f$ form a second component, and $g$ is isolated. Determine the edge count from the formula and check it directly.

There are $n=|V|=7$ vertices. The three components are $\{a,b,c,d\}$, $\{e,f\}$, and $\{g\}$, so $c=3$. Substituting gives $$ n-c=7-3=4. $$ Thus the formula predicts four edges.

Directly counting the specified edge set gives $E=\{ab,bc,cd,ef\}$, which contains four edges. Component by component, the first component has four vertices and three listed edges, the second has two vertices and one listed edge, and the isolated vertex has one vertex and zero edges. The sum is $3+1+0=4$, agreeing with $n-c$.

Check: the component sizes sum to $4+2+1=7=n$, and their edge counts sum to $3+1+0=4=7-3$. The isolated vertex contributes to $n$ and $c$, but not to $|E|$.

Worked Example: A Forest with Three Nontrivial Components

Let $H=(V,E)$, where $V=\{1,2,3,4,5,6,7,8,9\}$ and $E=\{12,23,34,45,67,89\}$. The components have vertex sets $\{1,2,3,4,5\}$, $\{6,7\}$, and $\{8,9\}$. Find the predicted edge count and verify it using the component sizes.

Here $n=9$ and $c=3$, so $$ n-c=9-3=6. $$ The edge list has six entries: $12,23,34,45,67,89$. Independently, the component sizes are $5,2,2$. Their tree edge counts are $5-1=4$, $2-1=1$, and $2-1=1$, respectively. Adding these gives $4+1+1=6$, as predicted.

Check: the vertex counts add to $5+2+2=9$, and the component edge counts add to $4+1+1=6=9-3$. Each listed edge stays within one of the stated vertex sets, and the edges in each set connect all its vertices without closing a cycle.

Worked Example: A Forest Consisting Only of Isolated Vertices

Let $J=(V,E)$, where $V=\{p,q,r,s\}$ and $E=\varnothing$. Determine $n$, $c$, and the edge count.

There are $n=4$ vertices. Because there are no edges, no two distinct vertices are connected by a path, so each vertex is its own component. Thus $c=4$, and the formula gives $$ n-c=4-4=0. $$ The edge set is empty, so direct counting also gives $|E|=0$.

Check: the four component sizes are $1,1,1,1$, and each contributes $1-1=0$ edges. Their total is $0+0+0+0=0$, the same as the direct count.

Reading the Formula Correctly

The statement uses the number of connected components, not the number of vertices of positive degree. An isolated vertex is still a component. The empty graph is a different boundary case: it has no vertices and no components, so the formula returns zero edges without needing a special adjustment.

Another way to use the proof is to add component contributions. If a forest has component sizes $k_1,\ldots,k_c$, then each component contributes $k_i-1$ edges, and summing gives $$ (k_1-1)+\cdots+(k_c-1) =(k_1+\cdots+k_c)-c =n-c. $$ This is a count, not a test that an arbitrary graph is a forest. The theorem assumes the graph is acyclic; the edge count alone does not establish that assumption.

Common Mistake: Forgetting Isolated Components

For the graph in the first example, a mistaken calculation might count only the two components containing edges and write $c=2$. It would then give $n-c=7-2=5$, which disagrees with the four edges listed. The correction is to include $\{g\}$: it is a connected component even though it has no edges. With $c=3$, the calculation is $7-3=4$, matching the edge list.

A second frequent error is to apply the formula to a graph before checking that it is a forest. The proof uses the fact that each component is a tree. If a component contains a cycle, the tree lemma does not apply to it, so this argument gives no edge count for that graph.

Check Your Understanding

For each question, identify the vertex count and component count before applying the formula.

A forest has component sizes $6,3,1$. How many vertices and edges does it have?
Let $F$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,45\}$. List its components and verify the edge count formula.
Why does a one-vertex component contribute zero edges to the formula?
What are $n$, $c$, and $|E|$ for the empty graph, under the convention used here?
In the tree lemma’s induction step, why must the deleted endpoint have degree one?