Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The same question using a proof by contradiction was asked here. –  Douglas S. Stones Apr 12 '13 at 19:13
add comment

2 Answers

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.

share|improve this answer
add comment

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?

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.