If G is the forest with n vertices and k connected components, how many edges does G have? A. floor(n/k). B. ceil(n/k). ...

Question

If G is the forest with n vertices and k connected components, how many edges does G have? A. floor(n/k). B. ceil(n/k). C. n - k. D. n - k + 1.

Accepted Answer

n - k edges -> Option C. A forest is a collection of trees, and each tree on its own vertices has one fewer edge than vertices. Adding the (vertices - 1) over all k trees, the '-1's pile up to '-k', so the total is n - k edges.