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

A. |n/k|
B. (n - k)/2
C. n - k...

Question

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

A. |n/k|
B. (n - k)/2
C. n - k
D. n + k - 1

Accepted Answer

C. n - k A forest is an acyclic graph (a collection of trees). Each connected component is a tree. A tree on m vertices has exactly m - 1 edges. Summing over all k components: if component i has n_i vertices, it contributes n_i - 1 edges. Total edges = sum of (n_i - 1) = (sum of n_i) - k = n - k.

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