How many edges can there be in a forest with p components having n vertices in all?

GATE 1992 · Discrete Mathematics · Graph Connectivity · medium

Answer: A forest with n vertices and p components has exactly n - p edges.

1. Apply tree edge formula per component: Component i has n_i vertices => n_i-1 edges. Total = sum_{i=1}^{p}(n_i-1) = n - p.
2. Verify with the forest formula: Direct: edges = n - p. Example: n=8, p=3 => 5 edges. Three trees of sizes 4,2,2 have 3+1+1=5 edges. Correct.