Question

a) How many edges does a tree with \({\bf{n}}\) vertices have?

b) What do you need to know to determine the number of edges in a forest with \({\bf{n}}\) vertices?

Short answer

a) There are edges \({\bf{n - 1}}\)with \({\bf{n}}\) vertices.

b) You need to know the number of trees to determine the number of edges.

Step-by-step solution

Definition

A simple path is a path that does not contain the same edge more than once.

A circuit is a path that begins and ends in the same vertex.

A graph is connected if there exists a path between every pair of vertices.

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.

Simple circuits

A tree with \({\bf{n}}\) vertices always has \({\bf{n - 1}}\) edges (as the graph has to be connected which requires at least \({\bf{n - 1}}\) edges and as the graph cannot contain any simple circuits which requires at most \({\bf{n - 1}}\) edges).

Edges in the forest

To determine the number of edges in a forest with \({\bf{n}}\) vertices, we require to know the number of trees in the forest.

For example, if we know that a forest contains\({\bf{m}}\) trees and \({\bf{n}}\) vertices.

Let \({{\bf{n}}_{\bf{i}}}\) be the number of vertices in tree \({\bf{i}}\), then \({{\bf{n}}_{\bf{1}}}{\bf{ + }}{{\bf{n}}_{\bf{2}}}{\bf{ + \ldots + }}{{\bf{n}}_{\bf{k}}}{\bf{ = n}}{\bf{.}}\)

Tree \({\bf{i}}\) needs to have \({{\bf{n}}_{\bf{i}}}{\bf{ - 1}}\) edges by part \(\left( {\bf{a}} \right)\) and thus the forest then contains

\(\left( {{{\bf{n}}_{\bf{1}}}{\bf{ - 1}}} \right){\bf{ + }}\left( {{{\bf{n}}_{\bf{2}}}{\bf{ - 1}}} \right){\bf{ + \ldots + }}\left( {{{\bf{n}}_{\bf{m}}}{\bf{ - 1}}} \right){\bf{ = }}\left( {{{\bf{n}}_{\bf{1}}}{\bf{ + }}{{\bf{n}}_{\bf{2}}}{\bf{ + \ldots + }}{{\bf{n}}_{\bf{k}}}} \right){\bf{ - m = n - m}}\) edges.