A simple graph $G=(V,E)$ is a forest iff the number of components is $|V|-|E|$.
Let $|V| = n$ and $|E| = k$.
$\Rightarrow$ How can I use the fact that a simple graph on $n$ vertices and $k$ edges has at least $n-k$ components (I actually have the proof of this)? Do we have equality since adding more edges forms a cycle?
$\Leftarrow$
For the converse, if the graph has $|V|-|E|$ components, then each of the components should be a tree because each $n_i$-vertex tree contains $n_i-1$ edges. Is this a good enough argument?
Best Answer
For the first part assume that $G$ has $s$ components. Then as it's forest we have that each such component is a tree and hence if $V_1$ is the number of vertices in the first component then there are $V_1-1$ edges in it. Obviously the number of edges in G is given by:
$$|E| = \sum_{n=1}^s (V_n - 1) = \sum_{n=1}^s V_n - s = |V| - s \implies s = |V| - |E|$$
Hence we proved one direction. For the other direction we know that a connected component of a graph can have at least $V_i - 1$ edges, where $V_i$ is the number of vertices in that connected component. So as $G$ has $s=|V| - |E|$ components we have:
$$|E| \ge \sum_{n=1}^s (V_n - 1) = |V| - s = |E|$$
Because we have equality we get that equality must hold in each of the inequality, so each connected component has exactly $V_i - 1$ edges and hence it's a tree. As each connected component is a tree we have that $G$ is a forest.