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.

Prove that a graph with $n$ vertices and $m$ components and $n-m$ edges is a forest.

Using proof by contradiction, how would you go about this?

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

2 Answers 2

Assume that there is a cycle with $k$ edges. The graph on the entire vertex set containing only the edges of that cycle has $n-k+1$ components. Adding each of the remaining $n-m-k$ edges can only decrease the number of components by at most $1$, so after adding them all there are still at least $(n-k+1)-(n-m-k)=m+1$ components left.

share|improve this answer

Do you already know that a connected graph is a tree if and only if it has $n$ vertices and $n-1$ edges? If so, let the components of $G$ be $C_1,\dots,C_m$, with $n_1,\dots,n_m$ vertices respectively. If some $C_k$ had fewer than $n_k-1$ edges, it wouldn’t be connected: if you start with $n_k$ disconnected vertices and add one edge at a time, each edge reduces the number of components by at most $1$, so you need at least $n_k-1$ edges to connect all $n_k$ vertices. Thus, each $C_k$ has at least $n_k-1$ edges.

Now assume that some component is not a tree; renumber the components, if necessary, so that $C_1$ is not a tree. Then $C_1$ has more than $n_1-1$ edges, and $G$ therefore has at least

$$n_1+\sum_{k=2}^m(n_k-1)=n_1+\left(\sum_{k=2}^mn_k\right)-(m-1)=n-m+1$$

edges, contradiction the hypothesis that it has $n-m$ edges. Thus, every component must be a tree, and $G$ must be a forest.

(Note that the heart of this argument $-$ the proof that a connected graph with $k$ vertices must have at least $k-1$ edges $-$ uses exactly the same idea as Joriki’s proof.)

share|improve this answer

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.