If \(G\) is the forest with \(n\) vertices and \(k\) connected components, how…
2014
If \(G\) is the forest with \(n\) vertices and \(k\) connected components, how many edges does \(G\) have?
Answer: C. \(n-k\) — Key idea: a forest is a disjoint union of trees, and a tree with m vertices has m − 1 edges. Let the k connected components have vertex counts v1, v2, …, vk…
- A.
\(\left\lfloor\frac {n}{k}\right\rfloor\) - B.
\(\left\lceil \frac{n}{k} \right\rceil\) - C.
\(n-k\) - D.
\(n-k+1\)
Attempted by 359 students.
Show answer & explanation
Correct answer: C
Key idea: a forest is a disjoint union of trees, and a tree with m vertices has m − 1 edges.
Let the k connected components have vertex counts v1, v2, …, vk with v1 + v2 + … + vk = n.
Each component is a tree, so component i has vi − 1 edges. Summing gives total edges = (v1 − 1) + … + (vk − 1) = n − k.
Therefore the forest has n − k edges. Example: if n = 7 and k = 3, edges = 7 − 3 = 4.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2