How many edges are there in a forest with v vertices and k components?
2011
How many edges are there in a forest with v vertices and k components?
Answer: C. v − k — A forest is defined as a graph consisting of disjoint trees. In any tree with n vertices, there are exactly n - 1 edges. Since the forest has k components…
- A.
(v + 1) − k
- B.
(v + 1)/2 − k
- C.
v − k
- D.
v + k
Attempted by 224 students.
Show answer & explanation
Correct answer: C
A forest is defined as a graph consisting of disjoint trees. In any tree with n vertices, there are exactly n - 1 edges. Since the forest has k components summing to v vertices, the total edge count is the sum of (n_i - 1) for each component. This simplifies mathematically to v - k.
Explore the full course: Iocl Engineers Officers Grade A Paper 2
Loading lesson…