If $G$ is a forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: C) n - k

Graph Theory

A forest is a disjoint union of $k$ trees.

Let the $i$ -th connected component (tree) have $n_i$ vertices. A tree on $n_i$ vertices has exactly $n_i - 1$ edges.

The total number of vertices in the forest is:

\sum_{i=1}^{k} n_i = n

The total number of edges in the forest is:

\sum_{i=1}^{k} (n_i - 1) = \sum_{i=1}^{k} n_i - \sum_{i=1}^{k} 1 = n - k

Thus, the number of edges is $n - k$ , which corresponds to option (C).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Examiner trap

This Graph Theory previous year question is Q51 of the GATE CSE 2014 Set 3 paper. Find more GATE CSE PYQs on Graph Theory in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Graph Theory PYQs now with no account.

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Graph Theory has 21 GATE CSE PYQs across 14 papers from 2012 to 2026. 6 of them are 2-mark MCQs like this one, and GATE CSE 2014 Set 3 has 2.

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.