How many trees does a forest with n vertices and m edges contain?

Question

Concerning trees in graph theory:

How many trees does a forest with $n$ vertices and $m$ edges contain?

This has to do with combinatorics apparently but I'm struggling with these assignments since we skipped that topic.

I'm thinking it's related to $m-1$ or $n-1$ something.

Answer 1

First picture $n$ vertices with no edges. Then add the missing edges. Every time we add an edge, we combine two trees into one (as its vertices cannot come from the same tree - prove this). Therefore we end up with $n-m$ trees.

Answer 2

I think it's easier to go the other way around, i.e. how many edges does a forest with $k$ trees have ?

A tree with $n$ vertices has $n - 1$ edges.

Say your forest has $k$ trees. Denote by $n_1, n_2, \ldots, n_k$ the number of vertices of each tree. Thus the $i$-th tree has $n_i - 1$ edges. Summing up, the total number of edges is

$$ \sum_{i = 1}^k (n_i - 1) = \sum_{i = 1}^k n_i - \sum_{i = 1}^k 1 = n - k $$

So if the number of edges is $m$, we have $m = n - k$ and $k = n - m$.