GATE CS 2014 Set 3 Q51 — Graphs: Connectivity, Matching, Colouring

A forest is an acyclic graph where each connected component is a tree.

Let the forest $G$ have $k$ connected components, denoted by $T_1, T_2, \dots, T_k$. Let $n_i$ be the number of vertices in the component $T_i$ for $1 \le i \le k$.

Since the components partition the vertex set of $G$, the total number of vertices $n$ is:

Since each component $T_i$ is a tree, the number of edges in $T_i$ is $n_i - 1$. Therefore, the total number of edges $e$ in the forest $G$ is the sum of the edges in all components:

Thus, the forest has $n - k$ edges.

Hence, the correct option is C.