Proving number of edges in $F = n - k$

Question

So if we let $F = (V,E)$ be a forest with $n$ vertices and $k$ connected components (trees), how can I prove that the number of edges in $F = n - k$ ?

I was thinking of using induction, but I'm super lost. Can anyone guide me through this step by step? Would really appreciate it, thanks!

Answer 1

We note a tree $T$ with $n$ vertices has $n-1$ edges. So let $F = \bigcup_{i=1}^{k} T_{i}$ be the forest- a union of trees. Let $n_{i}$ be the number of vertices in each tree. So we have:

$|V(F)| = \sum_{i=1}^{k} n_{i} = n$

Since each component of the forest is a tree, we have $n_{i} - 1$ edges for $T_{i}$, giving us:

$|E(F)| = \sum_{i=1}^{k} (n_{i} - 1) = n - k$.

Answer 2

There is one more way of thinking about this problem:

We know that an $n$ node tree has $n-1$ edges. If you now want to convert this $n$ node tree to a $k$-tree forest, you have to remove $k-1$ edges from it.

So the number of edges in a $k$-tree forest with $n$ nodes would be: $n-1-(k-1) = n-k$