graph theory and forests

Question

We were given an this question in my class:

Prove that a forest with n vertices and m components has n-m edges using induction on m.

Induction is not my strongest point and I was wondering if anyone could help me out with this?

Answer 1

Suppose there is only one component. ($m = 1$). This is the case where our forest is a tree, and let us take for granted that a tree with $n$ vertices's, has $n - 1$ edges. Assuming, that every forest with $ m$ component and $n$ vertices has a $m - n$ vertices, we need to show that a forest with $n$ vertices's and $m + 1$ component, has a $n- m -1$. Now, take a two component of such a forest and simply add an edge between two roots of these components. Then we get a forest with $n$ vertices's and $m$ component, which by the hypotheses of our induction, should have a $n - m$ edges, To count the number of edges in our original forest, just subtract this added edge, i.e. a forest with $n$ vertices and $m+ 1$ component has a $n - m - 1$ edges.

Answer 2

Hints:

1. How many edges are there in a tree (i.e. a forest with one component) on $n$ vertices?

2. Given a forest on $n$ vertices with $m$ components, what can you do to get a forest on $n$ vertices with $m-1$ components?