Question

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

Answer 1

Answer: (C)

Explanation: Each component will have n/k vertices (pigeonhole principle). Hence, for each component there will be (n/k)-1 edges.

Since there are k components, total number of edges= k*((n/k)-1) = n-k.