# graph theory and forests

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?

-
The same question using a proof by contradiction was asked here. –  Douglas S. Stones Apr 12 '13 at 19:13

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?

-
I would have expected $m+1$ rather than $m-1$ in your second hint, given that you are suggesting starting with a tree. –  Tara B Sep 14 '12 at 11:18
I think it's logically cleaner in the inductive step to reduce the number of components. That way you don't have to worry about whether every $m+1$ component forest can be obtained from an $m$ component forest by the operation I'm hinting at. It's true that they can, but why prove it if you don't have to. –  Matt Pressland Sep 14 '12 at 11:25
True. $\hspace{0cm}$ –  Tara B Sep 14 '12 at 13:02

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.

-