Worked Forest Edge Counts from Components

Counting Edges One Component at a Time

A forest may consist of several separate trees, including components that are isolated single vertices. To calculate its total number of edges, count the edges in each component and add them. The key detail is that every component contributes one fewer edge than it has vertices. Thus a component with one vertex contributes zero edges, but it still counts as a component.

All graphs in this tutorial are finite and simple. A forest is a graph with no cycles. A connected component is a maximal connected subgraph; different components have no edges between them. An isolated vertex is a vertex with degree zero, and it forms a component by itself.

Definition: For a forest $G=(V,E)$, let $n=|V|$ be its number of vertices, $m=|E|$ its number of edges, and $c$ its number of connected components. In this tutorial, assume $n\ge1$, so $c\ge1$.

The component count is not the number of nontrivial pieces, nor the number of components that contain edges. Every component is counted, including each isolated vertex separately. We will use the established tree edge-count fact that a tree with $q$ vertices has $q-1$ edges. A one-vertex component is a tree with $q=1$, so this fact gives $1-1=0$ edges for it.

The Forest Edge-Count Formula

Theorem: If a forest has $n$ vertices, $m$ edges and $c$ connected components, then $$ m=n-c. $$ More precisely, if its components have $n_1,n_2,\dots,n_c$ vertices, then $$ m=\sum_{i=1}^{c}(n_i-1)=\left(\sum_{i=1}^{c}n_i\right)-c=n-c. $$

Proof. Each component of a forest is connected and has no cycle, so it is a tree. By the tree edge-count fact, component $i$ has $n_i-1$ edges. The components partition the vertices, so $\sum_{i=1}^{c} n_i=n$. They also partition the edges, since no edge joins two different components. Therefore $m=\sum_{i=1}^{c}(n_i-1)=\sum_{i=1}^{c}n_i-c=n-c$, as required. If a component is an isolated vertex, its $n_i$ is $1$, and its contribution $n_i-1$ is $0$; the calculation includes it without an exception. $\square$

This gives two useful ways to calculate. If the component sizes are known, calculate $n_i-1$ for each and add. If only $n$ and $c$ are known, subtract the component count from the vertex count. The subtraction is exact because every component uses one of the vertices as the “one fewer” adjustment.

Corollary: For a forest with $n\ge1$ vertices and $m$ edges, the number of connected components is $c=n-m$.

Proof. The theorem gives $m=n-c$. Adding $c$ to both sides and subtracting $m$ from both sides yields $c=n-m$. The value counts all components, including isolated vertices. $\square$

In a numerical problem, this corollary can either answer a question about the component count or check a proposed one. It applies when the graph is known to be a forest. Without that condition, the equation is not justified by this theorem.

Worked Counts

Worked Example: Two Isolated Vertices

Let $G=(V,E)$, where $V=\{1,2,3,4,5,6,7,8,9\}$ and $E=\{12,23,45,56,67\}$. Find the number of edges using the component sizes.

The first component has vertices $\{1,2,3\}$ and edges $12,23$, so its size is $3$ and its edge count is $3-1=2$. The second has vertices $\{4,5,6,7\}$ and edges $45,56,67$, so its size is $4$ and its edge count is $4-1=3$. Vertices $8$ and $9$ have no incident edges. Each is a component of size $1$, contributing $1-1=0$ edges.

There are $c=4$ components altogether: the two nontrivial components and the two isolated vertices. The vertex count is $n=9$, so the formula gives $m=n-c=9-4=5$. Counting the listed edges directly gives $2+3=5$, which agrees.

Check: The component contributions are $2,3,0,0$, whose sum is $2+3+0+0=5$. The isolated vertices add to the component count, not to the edge count.

Worked Example: Adding Component Contributions

Let $G=(V,E)$, where $V=\{a,b,c,d,e,f,g,h,i,j,k,l\}$ and $E=\{ab,bc,cd,ef,fg,hi,jk\}$. Find the number of edges by identifying every component.

The components are $\{a,b,c,d\}$, $\{e,f,g\}$, $\{h,i\}$, $\{j,k\}$, and $\{l\}$. Their sizes are $4,3,2,2,1$, so there are $c=5$ components. The corresponding edge counts are $4-1=3$, $3-1=2$, $2-1=1$, $2-1=1$, and $1-1=0$. Adding those values gives $3+2+1+1+0=7$.

As a second calculation, the graph has $n=12$ vertices, so $n-c=12-5=7$. The edge list also has eight? No: reading it carefully, the listed edges are $ab,bc,cd,ef,fg,hi,jk$, which number $3+2+1+1=7$. The component calculation and direct edge count agree.

Check: The component sizes sum to $4+3+2+2+1=12$, and their edge contributions sum to $7$. In particular, the one-vertex component $\{l\}$ accounts for a vertex and a component, but no edge.

Worked Example: Recovering the Component Count

A forest $G=(V,E)$ has $V=\{1,2,3,4,5,6,7,8,9,10,11\}$ and $E=\{12,23,45,56,67,89,10\,11\}$. Find the number of components in two ways.

First, the edge list separates into the vertex sets $\{1,2,3\}$, $\{4,5,6,7\}$, $\{8,9\}$, and $\{10,11\}$. These are four components, with sizes $3,4,2,2$. Their edge counts are $3-1=2$, $4-1=3$, $2-1=1$, and $2-1=1$. The sum is $2+3+1+1=7$, matching the seven listed edges.

For the second calculation, $n=11$ and $m=7$. The corollary gives $c=n-m=11-7=4$. This matches the count from the component sets.

Check: The component sizes add to $3+4+2+2=11$, and the edges within them add to $2+3+1+1=7$. Both counts use exactly the vertices and edges in the stated graph.

Why the Component Count Matters

The formula $m=n-c$ is sensitive to $c$: increasing the claimed number of components by one decreases the calculated edge count by one. A component-count error can therefore produce a plausible-looking answer that is nevertheless wrong. Isolated vertices are a frequent source of this error because they do not appear in the edge list as endpoints of any edge.

Worked Example: The Cost of Omitting Isolated Components

Use the graph from the first example: $V=\{1,2,3,4,5,6,7,8,9\}$ and $E=\{12,23,45,56,67\}$. Its components are $\{1,2,3\}$, $\{4,5,6,7\}$, $\{8\}$, and $\{9\}$. Suppose someone counts only the components containing edges, and reports $c=2$.

The incorrect calculation is $m=n-c=9-2=7$. This is two more than the actual edge count because two isolated components were omitted. The correct count is $c=2+1+1=4$, and hence $m=9-4=5$. Directly, the edge list contains $12,23,45,56,67$, exactly five edges.

Check: The incorrect count of $7$ would require two additional edges beyond the five actually listed. Nothing in the graph supplies those edges; the error came solely from using $2$ instead of $4$ components.

A reliable procedure is to identify all connected components before substituting numbers. In particular, check every vertex that does not occur in the edge list: each such vertex is isolated and contributes one component. Then calculate $n-c$, and, when an edge list is available, count its edges directly as a check.

List the components.
Include each isolated vertex as a component of size one.

Count vertices and components.
Record $n$ and the total component count $c$.

Calculate and check.
Use $m=n-c$, or add $n_i-1$ over the components, and compare with a direct count of listed edges when possible.

Common Mistakes

Leaving isolated vertices out of $c$. An isolated vertex is a connected component by itself. It contributes zero edges, but it must be included when calculating $n-c$. The fourth worked example shows that omitting two isolated vertices changes the result by two.

Subtracting the number of nontrivial components. The formula uses the number of all components, not just those with at least one edge. First identify every component, then count them.

Using the formula without checking the forest condition. The derivation depends on each component being a tree and thus having one fewer edge than vertices. The calculation $n-c$ should be used here only when the graph is known to be a forest.

Confusing vertices with components. The total vertex count is the sum of the component sizes, while the edge count is the sum of one less than each size. For sizes $n_1,\dots,n_c$, write both sums explicitly: $\sum_{i=1}^{c}n_i=n$ and $\sum_{i=1}^{c}(n_i-1)=m$.

Check Your Understanding

In each question, count isolated vertices as components. State your reasoning, not just the numerical answer.

A forest has $14$ vertices and $5$ components. How many edges does it have?
A forest has $10$ vertices and $6$ edges. How many connected components does it have?
Let $V=\{a,b,c,d,e,f,g\}$ and $E=\{ab,bc,de\}$. List all components and calculate the number of edges from their sizes.
A forest has component sizes $5,3,1,1$. Calculate its total number of vertices and edges.
Explain why an isolated vertex changes $n$ and $c$ by the same amount, but does not change $m$.