Problem
COM-B2-M07-P006 Edges in a Forest
#6
★★★☆☆ Level 3 of 5
A forest has \(n\) vertices and \(c\) connected components. Prove that it has \(n-c\) edges.
Each component of a forest is a tree.
Let the components have \(n_1,n_2,\ldots,n_c\) vertices. Each component is a tree, so it has \(n_i-1\) edges. The total number of edges is
\[\sum_{i=1}^c(n_i-1)=\sum_{i=1}^c n_i-c=n-c.\]
Often used to count components through edges.