Question

How many edges are there in a forest of \({\bf{t}}\) trees containing a total of \({\bf{n}}\) vertices?

Short answer

The forest contains n-t edges.

Step-by-step solution

Definition

A tree is an undirected graph that is connected and that does not contain any simple circuits.

A forest is a group of trees that are not connected with each other.

Theorem 2 A tree with n vertices has n-1 edges.

Finding the total of all vertices

Given: A forest of t trees containing a total of n vertices.

Let us assume that tree i contains \({n_i}\) vertices. The total of all vertices has to be equal to n vertices.

\({n_1} + {n_2} + \ldots + {n_t} = n\).

Using the tree theorem

By theorem tree \({\bf{i}}\) with \({n_i}\) vertices has \({n_i} - 1\) edges.

The number of edges in the forest is then the sum of the number of edges in each tree.

\(1 + 1 + \ldots + 1\)contains t ones \({n_1} + {n_2} + \ldots + {n_t} = n\)

\(\begin{array}{c}\left( {{n_1} - 1} \right) + \left( {{n_2} - 1} \right) + \ldots + \left( {{n_t} - 1} \right) = \left( {{n_1} + {n_2} + \ldots + {n_t}} \right) - (1 + 1 + \ldots + 1)\\ = \left( {{n_1} + {n_2} + \ldots + {n_t}} \right) - t\\ = n - t\end{array}\)

Thus, we then note that the forest contains \({\bf{n - t}}\) edges.