= Solution
{c}
Within each connected component with $n_i$ vertices, grow a tree by starting at one vertex and repeatedly adding an edge to an unreached vertex. Connectedness guarantees such an edge until every vertex has been reached. Exactly $n_i-1$ edges are added, so the component contains at least that many edges. Summing over the $k$ components gives
$$
\boxed{m\geq\sum_{i=1}^k(n_i-1)=n-k.}
$$
The selected trees form a <spanning forest>, and equality holds precisely when the original graph itself is a forest.
Back to article page
